Submission #1627686

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#define mp make_pair
#define int long long
using namespace std;

typedef pair<int,int> P;
typedef pair<int,P> PP;

signed main(){
	int n,w,c,a[100],b[100],dp[2][51][10001] = {};
	vector<int> col[50];
	cin >> n >> w >> c;
	for(int i = 0;i < n;i++){
		int t;
		cin >> a[i] >> b[i] >> t;
		col[t - 1].push_back(i);
	}
	for(int i = 0;i < 50;i++){
		int now = i % 2,next = (i + 1) % 2;
		for(int j = 0;j <= c;j++){
			for(int m : col[i]){
				int nxt[10001] = {};
				for(int k = 0;k <= w;k++){
					if(k + a[m] <= w) nxt[k + a[m]] = max(nxt[k + a[m]],max(dp[now][j][k],dp[next][j + 1][k]) + b[m]);
				}
				for(int k = 0;k <= w;k++) dp[next][j + 1][k] = max(dp[next][j + 1][k],nxt[k]);
			}
			for(int k = 0;k <= w;k++) dp[next][j][k] = max(dp[next][j][k],dp[now][j][k]);
		}
		for(int j = 0;j <= c;j++){
			for(int k = 0;k <= w;k++){
				dp[now][j][k] = 0;
			}
		}
	}
	int ma = 0;
	for(int i = 0;i <= c;i++){
		for(int j = 0;j <= w;j++) ma = max(ma,dp[0][i][j]);
	}
	cout << ma << endl;
	return 0;
}

Submission Info

Judge Result