結果
問題 |
No.448 ゆきこーだーの雨と雪 (3)
|
ユーザー |
![]() |
提出日時 | 2021-03-31 22:36:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,383 bytes |
コンパイル時間 | 1,906 ms |
コンパイル使用メモリ | 170,896 KB |
実行使用メモリ | 12,552 KB |
最終ジャッジ日時 | 2024-12-15 20:29:58 |
合計ジャッジ時間 | 55,282 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 3 |
other | WA * 20 TLE * 15 |
ソースコード
#include <bits/stdc++.h> using namespace std; int find(vector<int> T,int value){ int min=-1; int max=T.size(); int mid; while(max-min>1){ mid=(max+min)/2; if(T[mid]>value){ max=mid; }else{ min=mid; } } return min; } int main(){ int N,K; cin>>N>>K; vector<int> T(N),D(N); for(int i=0;i<N;i++){ cin>>T[i]>>D[i]; } int m=0; int M=1000000001; int mid; int prev; while(M-m>1){ mid=(m+M)/2; prev=-K; for(int i=0;i<N;i++){ if(mid<D[i]){ if(T[i]-prev<K){ m=mid; goto end; } prev=T[i]; } } M=mid; end:{} } vector<long long> dp(N); int ind; long long s=0; for(int i=0;i<N;i++){ s+=D[i]; } for(int i=0;i<N;i++){ ind=find(T,T[i]-K); if(D[i]>m){ if(ind==-1){ dp[i]=s-D[i]; }else{ dp[i]=dp[ind]-D[i]; } }else{ if(i==0){ dp[i]=s-D[i]; }else if(ind==-1){ dp[i]=min(s-D[i],dp[i-1]); }else{ dp[i]=min(dp[ind]-D[i],dp[i-1]); } } } cout<<m<<endl; cout<<dp[N-1]<<endl; }