結果
問題 | No.1037 exhausted |
ユーザー |
![]() |
提出日時 | 2020-04-24 22:06:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 49 ms / 2,000 ms |
コード長 | 1,075 bytes |
コンパイル時間 | 2,449 ms |
コンパイル使用メモリ | 199,768 KB |
最終ジャッジ日時 | 2025-01-09 23:50:48 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define modulo 1000000007 #define mod(mod_x) ((((long long)mod_x+modulo))%modulo) #define Inf 1000000000000000001 int main(){ int N,V,L; cin>>N>>V>>L; vector<int> x,v,w; x.push_back(0); v.push_back(0); w.push_back(0); for(int i=0;i<N;i++){ int a,b,c; cin>>a>>b>>c; x.push_back(a); v.push_back(b); w.push_back(c); } x.push_back(L); v.push_back(0); w.push_back(0); N = x.size(); vector<vector<long long>> dp(N,vector<long long>(V+1,Inf)); dp[0][V] = 0; for(int i=0;i<N-1;i++){ for(int j=V;j>=0;j--){ int to = min(j+v[i],V); dp[i][to] = min(dp[i][to],dp[i][j]+w[i]); } for(int j=0;j<=V;j++){ if(dp[i][j]==Inf)continue; int to = j - (x[i+1]-x[i]); if(to<0)continue; dp[i+1][to] = min(dp[i+1][to],dp[i][j]); } } /* for(int i=0;i<N;i++){ for(int j=0;j<=V;j++){ cout<<dp[i][j]<<','; } cout<<endl; } */ long long ans = Inf; for(int i=0;i<=V;i++){ ans = min(ans,dp.back()[i]); } if(ans==Inf)cout<<-1<<endl; else cout<<ans<<endl; return 0; }