| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 55 | 22 | 20 | 43.478% |
JOI 高校の生徒である葵は,1ドル$ から $N$ までの番号が付けられた $N$ 台のスマートフォンをレンタルしてお り,それぞれのスマートフォンには使用日数制限が設けられている.スマートフォン $i$ (1ドル ≦ i ≦ N$) は,明日 を 1ドル$ 日目としたとき,$A_i$ 日目から $B_i$ 日目までの $B_i - A_i + 1$ 日のうち 1ドル$ 日単位で最大 $C_i$ 日まで選んで使用 することができる.このとき,使用する日は連続していなくても構わない.
今レンタルしているスマートフォンはすべて $K + 1$ 日目に返却しなくてはならない.そこで,葵はスマー トフォンを最大限使用するために明日から $K$ 日分の使用計画を立てようと思ったが,難しかったため,あ なたに頼むことにした.
葵がレンタルしているスマートフォンの台数 $N,ドル使用計画を立てる日数 $K,ドルそれぞれのスマートフォンの 使用日数制限が与えられる.葵が $K$ 日の間で 1ドル$ 台以上のスマートフォンを使用することのできる最大日数 を求めるプログラムを作成せよ.
入力は以下の形式で標準入力から与えられる.
$N$ $K$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_N$ $B_N$ $C_N$
標準出力に,葵が 1ドル$ 台以上のスマートフォンを使用することのできる最大日数を 1ドル$ 行で出力せよ.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | $N ≦ 1,000円,ドル $K ≦ 1,000円,ドル $B_i < A_j$ または $B_j < A_i$ (1ドル ≦ i < j ≦ N$). |
| 2 | 10 | $C_i = B_i - A_i + 1$ (1ドル ≦ i ≦ N$). |
| 3 | 10 | $N ≦ 1,000円,ドル $K ≦ 1,000円,ドル $A_i = 1$ (1ドル ≦ i ≦ N$). |
| 4 | 30 | $N ≦ 1,000円,ドル $K ≦ 1,000円$. |
| 5 | 15 | $K ≦ 300,000円$. |
| 6 | 30 | 追加の制約はない. |
5 15 1 6 3 2 3 1 2 2 1 3 7 3 11 13 2
9
例えば次のようにすると,葵は 9ドル$ 日 1ドル$ 台以上のスマートフォンを使用することができる.この表におい て,〇 ,× はそれぞれ該当のスマートフォンを使う日,使わない日を表す.
| 日数 | 1ドル$ | 2ドル$ | 3ドル$ | 4ドル$ | 5ドル$ | 6ドル$ | 7ドル$ | 8ドル$ | 9ドル$ | 10ドル$ | 11ドル$ | 12ドル$ | 13ドル$ | 14ドル$ | 15ドル$ |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| スマートフォン 1ドル$ | 〇 | × | × | 〇 | 〇 | × | |||||||||
| スマートフォン 2ドル$ | × | 〇 | |||||||||||||
| スマートフォン 3ドル$ | 〇 | ||||||||||||||
| スマートフォン 4ドル$ | × | × | 〇 | 〇 | |||||||||||
| スマートフォン 5ドル$ | × | 〇 | 〇 |
10ドル$ 日以上 1ドル$ 台以上のスマートフォンを使用することはできないので,9ドル$ を出力する.
この入力例は小課題 4, 5, 6 の制約を満たす.
4 8 1 2 2 1 3 3 1 3 3 1 5 5
5
例えば次のようにすると,葵は 5ドル$ 日 1ドル$ 台以上のスマートフォンを使用することができる.この表において,〇 ,× はそれぞれ該当のスマートフォンを使う日,使わない日を表す.
| 日数 | 1ドル$ | 2ドル$ | 3ドル$ | 4ドル$ | 5ドル$ | 6ドル$ | 7ドル$ | 8ドル$ |
|---|---|---|---|---|---|---|---|---|
| スマートフォン 1ドル$ | 〇 | 〇 | ||||||
| スマートフォン 2ドル$ | 〇 | 〇 | 〇 | |||||
| スマートフォン 3ドル$ | × | × | × | |||||
| スマートフォン 4ドル$ | 〇 | 〇 | 〇 | 〇 | 〇 |
6ドル$ 日以上 1ドル$ 台以上のスマートフォンを使用することはできないので,5ドル$ を出力する.
この入力例は小課題 2, 3, 4, 5, 6 の制約を満たす.
3 6 1 1 1 2 3 2 4 6 2
5
この入力例は小課題 1, 4, 5, 6 の制約を満たす.
3 7 4 6 3 4 6 1 4 6 2
3
この入力例は小課題 4, 5, 6 の制約を満たす.
15 4768558 3025257 4432949 1319859 3066618 4509446 1254699 3417684 3665318 139375 914550 2131942 1143715 729276 928089 139749 4634629 4763389 30565 3554868 4214881 168515 3206967 4721972 519481 4595561 4755647 139316 1423715 2437121 87927 2355901 3933477 584228 3076814 3150827 40891 3280648 3632366 177447 2224458 2296486 47900 2693763 4283443 832253
3826780
この入力例は小課題 6 の制約を満たす.