結果
問題 | 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 1000000000000000001int 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;}