結果
問題 |
No.448 ゆきこーだーの雨と雪 (3)
|
ユーザー |
![]() |
提出日時 | 2025-01-03 19:40:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 891 bytes |
コンパイル時間 | 4,089 ms |
コンパイル使用メモリ | 39,168 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2025-01-03 19:41:05 |
合計ジャッジ時間 | 5,772 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 9 WA * 26 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:18:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 18 | scanf("%d %d",&n,&k); | ~~~~~^~~~~~~~~~~~~~~ main.cpp:19:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 19 | for(int i=1;i<=n;i++) scanf("%d %d",&a[i].t,&a[i].d); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include<cstdio> #include<algorithm> using namespace std; const int N=2e5+10; int n,k,dp[N]; struct Work { int t,d; }a[N]; bool check(int x) { int lst=-1e9; for(int i=1;i<=n;i++) { if(a[i].d<=x) continue; if(a[i].t-lst<k) return false; lst=a[i].t; } return true; } int main() { //freopen("help.in","r",stdin); //freopen("help.out","w",stdout); scanf("%d %d",&n,&k); for(int i=1;i<=n;i++) scanf("%d %d",&a[i].t,&a[i].d); int l=0,r=1e9,ans=1e9; while(l<=r) { int mid=(l+r)>>1; if(check(mid)) ans=mid,r=mid-1; else l=mid+1; } printf("%d\n",ans); for(int i=2;i<=n+1;i++) dp[i]=-1e9; int sum=0; for(int i=1,p=0;i<=n;i++) { while(a[i].t-a[p].t>=k) p++; if(!p||a[i].t-a[p-1].t>=k) dp[i+1]=max(dp[i+1],dp[p]+a[i].d); if(a[i].d<=ans) dp[i+1]=max(dp[i+1],dp[i]); else p=i+1; sum+=a[i].d; } printf("%d",sum-dp[n+1]); return 0; }