結果
問題 | No.448 ゆきこーだーの雨と雪 (3) |
ユーザー | koba-e964 |
提出日時 | 2016-11-18 23:33:20 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 173 ms / 2,000 ms |
コード長 | 1,745 bytes |
コンパイル時間 | 688 ms |
コンパイル使用メモリ | 92,956 KB |
実行使用メモリ | 13,516 KB |
最終ジャッジ日時 | 2023-09-02 12:51:26 |
合計ジャッジ時間 | 5,391 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 3 ms
4,380 KB |
testcase_07 | AC | 1 ms
4,380 KB |
testcase_08 | AC | 2 ms
4,380 KB |
testcase_09 | AC | 2 ms
4,376 KB |
testcase_10 | AC | 2 ms
4,376 KB |
testcase_11 | AC | 2 ms
4,380 KB |
testcase_12 | AC | 2 ms
4,376 KB |
testcase_13 | AC | 25 ms
4,504 KB |
testcase_14 | AC | 28 ms
4,688 KB |
testcase_15 | AC | 70 ms
7,160 KB |
testcase_16 | AC | 115 ms
9,836 KB |
testcase_17 | AC | 122 ms
10,472 KB |
testcase_18 | AC | 21 ms
4,376 KB |
testcase_19 | AC | 157 ms
12,452 KB |
testcase_20 | AC | 57 ms
6,472 KB |
testcase_21 | AC | 156 ms
12,560 KB |
testcase_22 | AC | 58 ms
6,500 KB |
testcase_23 | AC | 159 ms
12,356 KB |
testcase_24 | AC | 39 ms
5,324 KB |
testcase_25 | AC | 158 ms
12,380 KB |
testcase_26 | AC | 19 ms
4,384 KB |
testcase_27 | AC | 118 ms
10,272 KB |
testcase_28 | AC | 109 ms
9,592 KB |
testcase_29 | AC | 62 ms
6,752 KB |
testcase_30 | AC | 163 ms
12,700 KB |
testcase_31 | AC | 25 ms
4,444 KB |
testcase_32 | AC | 27 ms
4,684 KB |
testcase_33 | AC | 173 ms
13,288 KB |
testcase_34 | AC | 171 ms
13,132 KB |
testcase_35 | AC | 173 ms
13,136 KB |
testcase_36 | AC | 167 ms
13,132 KB |
testcase_37 | AC | 172 ms
13,148 KB |
testcase_38 | AC | 171 ms
13,516 KB |
ソースコード
#include <algorithm> #include <bitset> #include <cassert> #include <cctype> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> #define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++) using namespace std; typedef long long int ll; typedef vector<int> VI; typedef vector<ll> VL; typedef pair<int, int> PI; const ll mod = 1e9 + 7; const int N = 200100; int n; ll t[N], d[N]; int get_pos(ll time) { int idx = upper_bound(t, t + n, time) - t; return idx; } int main(void){ ll k; cin >> n >> k; REP(i, 0, n) { cin >> t[i] >> d[i]; } ll lo = -1, hi = 2e9; while (hi - lo > 1) { ll mid = (hi + lo) / 2; VL overfull; REP(i, 0, n) { if (d[i] > mid) { overfull.push_back(t[i]); } } // Yuki has to do jobs in overfull. bool ok = 1; REP(i, 0, overfull.size() - 1) { ok &= overfull[i + 1] - overfull[i] >= k; } if (ok) { hi = mid; } else { lo = mid; } } cout << hi << endl; typedef pair<ll, ll> PL; vector<PL> dp(n + 1), ma_acc(n + 1); dp[0] = PL(0, 0); ma_acc[0] = PL(0, 0); REP(i, 0, n) { PL res(0,0); res = max(res, dp[i]); PL sub2 = ma_acc[get_pos(t[i] - k)]; sub2.second += d[i]; if (d[i] > hi) { // Yuki does this. sub2.first += 1; } res = max(res, sub2); dp[i + 1] = res; ma_acc[i + 1] = max(ma_acc[i], res); } ll tot = -dp[n].second; REP(i, 0, n) { tot += d[i]; } cout << tot << endl; }