#470188 (C++17) No.1037 exhausted

• 問題: No.1037 exhausted
• ユーザー: fura
• 提出日時: 2020-04-25 05:29:25
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: RE
• 実行時間: -
• コード長: 895 bytes
• コンパイル時間: 2,053 ms
• コンパイル使用メモリ: 202,500 KB
• 実行使用メモリ: 35,072 KB
• 最終ジャッジ日時: 2024-10-15 20:16:54
• 合計ジャッジ時間: 3,821 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	3 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	2 ms; 5,248 KB
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	2 ms; 5,248 KB
testcase_07	AC	2 ms; 5,248 KB
testcase_08	AC	2 ms; 5,248 KB
testcase_09	AC	2 ms; 5,248 KB
testcase_10	AC	2 ms; 5,248 KB
testcase_11	AC	3 ms; 5,248 KB
testcase_12	AC	29 ms; 34,816 KB
testcase_13	AC	27 ms; 35,072 KB
testcase_14	AC	29 ms; 34,760 KB
testcase_15	AC	29 ms; 34,944 KB
testcase_16	AC	28 ms; 34,816 KB
testcase_17	AC	27 ms; 34,964 KB
testcase_18	AC	27 ms; 34,732 KB
testcase_19	AC	28 ms; 34,776 KB
testcase_20	AC	25 ms; 34,728 KB
testcase_21	RE	-
testcase_22	RE	-

ソースコード

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;
using lint=long long;

const long long INF=1LL<<61;

int main(){
	int n,V,L; scanf("%d%d%d",&n,&V,&L);
	vector<int> x(n+1),v(n+1),w(n+1);
	rep(i,n) scanf("%d%d%d",&x[i],&v[i],&w[i]);
	x[n]=L;

	// dp[i][j] = ( i 番目のガソリンスタンドまで行って, 残りガソリンが j リットルあるときの最小コスト)
	static lint dp[2001][2001];
	rep(i,n+2) rep(j,V+1) dp[i][j]=INF;
	dp[0][V]=0;
	rep(i,n+1){
		int j0;
		if(i==0) j0=x[0];
		else     j0=x[i]-x[i-1];

		for(int j=j0;j<=V;j++){
			// i 番目のガソリンスタンドで補充しない
			dp[i+1][j-j0]=min(dp[i+1][j-j0],dp[i][j]);
			// 補充する
			dp[i+1][min(j-j0+v[i],V)]=min(dp[i+1][min(j-j0+v[i],V)],dp[i][j]+w[i]);
		}
	}

	lint ans=*min_element(dp[n+1],dp[n+1]+V+1);
	printf("%lld\n",ans<INF?ans:-1);

	return 0;
}