結果
問題 |
No.448 ゆきこーだーの雨と雪 (3)
|
ユーザー |
![]() |
提出日時 | 2021-03-31 23:32:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,227 bytes |
コンパイル時間 | 1,964 ms |
コンパイル使用メモリ | 175,572 KB |
実行使用メモリ | 7,436 KB |
最終ジャッジ日時 | 2024-12-15 22:33:17 |
合計ジャッジ時間 | 18,157 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 2 WA * 32 TLE * 1 |
ソースコード
#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; } long long calc(vector<int> T,vector<int> D,int K){ if(T.size()==0){ return 0; } vector<long long> dp(T.size()); long long sum=0; int ind; for(int i=0;i<T.size();i++){ sum+=D[i]; } dp[0]=sum-D[0]; for(int i=1;i<T.size();i++){ ind=find(T,T[i]-K); if(ind==-1){ dp[i]=min(dp[ind]-D[i],dp[i-1]); }else{ dp[i]=min(sum-D[i],dp[i-1]); } } return dp[T.size()-1]; } 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=-1; 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<bool> isUsed(N); int pointer; for(int i=0;i<N;i++){ if(D[i]>M){ isUsed[i]=true; pointer=i-1; while(pointer>=0 && !isUsed[pointer] && T[i]-T[pointer]<K && D[pointer]<=M){ isUsed[pointer]=true; pointer--; } pointer=i+1; while(pointer<N && !isUsed[pointer] && T[pointer]-T[i]<K && D[pointer]<=M){ isUsed[pointer]=true; pointer++; } } } vector<int> tempT(0),tempD(0); long long ans=0; for(int i=0;i<N;i++){ if(isUsed[i]){ ans+=calc(tempT,tempD,K); tempT.resize(0); tempD.resize(0); if(D[i]<=M){ ans+=D[i]; } }else{ tempT.push_back(T[i]); tempD.push_back(D[i]); } } ans+=calc(tempT,tempD,K); cout<<M<<endl<<ans<<endl; }