結果
問題 | No.448 ゆきこーだーの雨と雪 (3) |
ユーザー |
![]() |
提出日時 | 2016-11-19 00:01:27 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 160 ms / 2,000 ms |
コード長 | 1,758 bytes |
コンパイル時間 | 628 ms |
コンパイル使用メモリ | 58,908 KB |
実行使用メモリ | 9,936 KB |
最終ジャッジ日時 | 2024-06-11 19:32:27 |
合計ジャッジ時間 | 4,553 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
//難しさの最大値=Tなら、T+1以上のタスクをYukiさんに頼んでそれ以外を自分でやると「Yukiさんの体にやさしい」 //それで無理なら答えはTを超える, OKなら答えはT以下。(st, ed]で2分探索できる. //難しさ(答え)を求めたら, 総和はちょっと工夫したDPで求まる。(こっちが本質!!) #include <iostream> #include <algorithm> #define int long long using namespace std; int n, k; int t[200000], d[200000]; bool mustWork[200000]; int mustWorkR[200001]; int dp[200001]; //dp[i] = 時刻t[i]からYukiさんを起こせる場合の, それまでにYukiさんがした仕事の量の最大 bool check(int mid) { int i; int now = -1145141919; for (i = 0; i < n; i++) { if (d[i] > mid) { if (now + k > t[i]) return false; now = t[i]; } } return true; } signed main() { int i; cin >> n >> k; for (i = 0; i < n; i++) { cin >> t[i] >> d[i]; } int st = -1, ed = 1000000000, mid; //(st, ed] while (ed - st >= 2) { mid = (st + ed) / 2; if (check(mid)) { ed = mid; } else { st = mid; } } cout << ed << endl; for (i = 0; i < n; i++) { mustWork[i] = (ed < d[i]); } for (i = 1; i <= n; i++) { mustWorkR[i] = mustWork[i-1] + mustWorkR[i-1]; } for (i = 0; i <= n; i++) { dp[i] = -1145141919893810; } dp[0] = 0; for (i = 0; i < n; i++) { int id = lower_bound(t, t + n, t[i] + k) - t; //もし, mustWork[i+1]~mustWork[id-1]内にtrueがあったら働いちゃだめ if (mustWorkR[id] - mustWorkR[i+1] == 0) { dp[id] = max(dp[id], dp[i] + d[i]); } if (!mustWork[i]) { dp[i + 1] = max(dp[i + 1], dp[i]); } } int ans = 0; for (i = 0; i < n; i++) { ans += d[i]; } ans -= dp[n]; cout << ans << endl; return 0; }