結果
問題 | No.448 ゆきこーだーの雨と雪 (3) |
ユーザー |
![]() |
提出日時 | 2017-08-20 17:55:38 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 156 ms / 2,000 ms |
コード長 | 2,422 bytes |
コンパイル時間 | 662 ms |
コンパイル使用メモリ | 91,056 KB |
実行使用メモリ | 8,884 KB |
最終ジャッジ日時 | 2024-10-14 17:32:54 |
合計ジャッジ時間 | 4,649 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
#include <cmath>#include <vector>#include <list>#include <map>#include <set>#include <functional>#include <queue>#include <iostream>#include <string.h>#include <iomanip>#include <algorithm>#include <functional>#include <cstdint>#include <climits>#include <unordered_set>#include <sstream>#include <stack>using namespace std;typedef long long int ll;typedef pair<int,int> pii;typedef tuple<ll,ll,ll> t3;using namespace std;int N,K;ll T[202020],D[202020];int NG[202020];ll dp[202020];int ok(int can) {int pre=-1<<30;for(int i = 0;i < N;i++){if(D[i]>can){if(T[i]-pre<K){return 0;}pre = (int)T[i];}}return 1;}void solve() {cin>>N>>K;for(int i = 0;i < N;i++) cin>>T[i]>>D[i];//2分探索で抑制できる最大のコストを計算する。int ma=(1<<30)-1;for(int i=29;i>=0;i--){ll arg = ma - (1 << i);if(ok(arg)){ma-=1<<i;//cout << "ok:" << arg << endl;}else{//cout << "ng:" << arg << endl;}}cout<<ma<<endl;//前後K時間中は無理なのでNGとするll pre=-1LL<<40;for(int i = 0;i < N;i++) {if(D[i]>ma) pre = T[i];else if(T[i]-pre<K) NG[i]=1;}pre=1LL<<40;for(int i=N-1;i>=0;i--) {if(D[i]>ma) pre = T[i];else if(pre-T[i]<K) NG[i]=1;}ll sum=0;for(int i = 0;i < N;i++) {if(D[i]>ma) {//yukiを起こすので0にするD[i]=0;}else{sum+=D[i];if(NG[i]){//のちのdpではコスト0としてカウントするD[i]=0;}}}ll tma=0;int x=0;for(int i = 0;i < N;i++){//尺取り法//ll tma = 0;//for(int j = 0;j < i;j++)//{// if(T[i]-T[j] >= K)// {// t = max(t, dp[j]);// }//}while(T[i]-T[x]>=K){++x;tma=max(tma,dp[x]);//cout << "while:" << i << "," << tma << endl;}dp[i+1]=max(dp[i], tma+D[i]);}cout<<sum-dp[N]<<endl;}int main(){solve();return 0;}