結果

問題 No.1947 質より種類数
コンテスト
ユーザー 沙耶花
提出日時 2022-05-20 21:43:30
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 174 ms / 2,000 ms
コード長 706 bytes
コンパイル時間 4,131 ms
コンパイル使用メモリ 251,072 KB
最終ジャッジ日時 2025-01-29 10:22:19
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf 1000000000


int main() {
    
	int N,V,C;
	cin>>N>>V>>C;
	
	vector<int> v(N),w(N);
	rep(i,N){
		cin>>v[i]>>w[i];
	//	w[i]+=C;
	}
	
	vector<int> dp(V+1,-Inf);
	dp[0] = 0;
	rep(i,N){
		vector<int> ndp(V+1,-Inf);
		rep(j,V+1){
			ndp[j] = max(ndp[j],dp[j]);
			if(j+v[i]<=V){
				ndp[j+v[i]] = max(ndp[j+v[i]],dp[j] + w[i] + C);
			}
		}
		rep(j,V+1){
			if(j-v[i]>=0){
				ndp[j] = max(ndp[j],ndp[j-v[i]]+w[i]);
			}
		}
		swap(dp,ndp);
	}
	
	int ans = 0;
	rep(i,V+1)ans = max(ans,dp[i]);
	cout<<ans<<endl;
	
    return 0;
}
0