結果
問題 | No.448 ゆきこーだーの雨と雪 (3) |
ユーザー |
![]() |
提出日時 | 2016-11-18 22:37:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 84 ms / 2,000 ms |
コード長 | 1,751 bytes |
コンパイル時間 | 2,285 ms |
コンパイル使用メモリ | 183,368 KB |
実行使用メモリ | 10,496 KB |
最終ジャッジ日時 | 2024-06-11 19:29:18 |
合計ジャッジ時間 | 4,982 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
#include "bits/stdc++.h" using namespace std; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL; typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll; template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; } template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; } int main() { int N; int K; while(~scanf("%d%d", &N, &K)) { vi time(N), diff(N); vpii dts(N); rep(i, N) { int T; int D; scanf("%d%d", &T, &D); time[i] = T; diff[i] = D; dts[i] = { D, T }; } sort(dts.rbegin(), dts.rend()); int maxD = -INF; { set<int> s; for(auto p : dts) { auto it = s.insert(p.second).first; ++ it; bool ok = true; if(it != s.end()) ok &= abs(p.second - *it) >= K; -- it; if(it != s.begin()) { -- it; ok &= abs(p.second - *it) >= K; } if(!ok) { maxD = p.first; break; } } } if(maxD == -INF) { puts("0\n0"); continue; } vector<int> ngcnt(N + 1); vector<ll> sum(N + 1); rep(i, N) { sum[i + 1] = sum[i] + diff[i]; ngcnt[i + 1] = ngcnt[i] + (diff[i] > maxD); } vector<ll> dp(N + 1, INFL); dp[0] = 0; rep(i, N) { ll x = INFL; int j = (upper_bound(time.begin(), time.end(), time[i] - K) - time.begin()); if(ngcnt[i] - ngcnt[j] == 0) amin(x, dp[j] + (sum[i] - sum[j])); if(diff[i] <= maxD) amin(x, dp[i] + diff[i]); dp[i + 1] = x; } ll ans = dp[N]; printf("%d\n%lld\n", maxD, ans); } return 0; }