Submission #60538406

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
#define int long long
#define f(i,j,n) for(int i=j;i<=n;i++)
#define updmax(a,b) a=max(a,b)
#define updmin(a,b) a=min(a,b)
#define XQZ
using namespace std;
int dp[2][510][50010];
int n,X,K;
struct acc{
  int p,u,c;
}w[511];
void gs(){
  cin>>n>>X>>K;
  f(i,1,n)cin>>w[i].p>>w[i].u>>w[i].c;
  sort(w+1,w+1+n,[&](acc a,acc b){
    return a.c<b.c;
  });
  int p=0;
  int ans=0;
  f(i,1,n){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>
#define int long long
#define f(i,j,n) for(int i=j;i<=n;i++)
#define updmax(a,b) a=max(a,b)
#define updmin(a,b) a=min(a,b)
#define XQZ
using namespace std;
int dp[2][510][50010];
int n,X,K;
struct acc{
	int p,u,c;
}w[511];
void gs(){
	cin>>n>>X>>K;
	f(i,1,n)cin>>w[i].p>>w[i].u>>w[i].c;
	sort(w+1,w+1+n,[&](acc a,acc b){
		return a.c<b.c;
	});
	int p=0;
	int ans=0;
	f(i,1,n){
		if(i!=1&&w[i].c!=w[i-1].c){
			f(j,0,X)updmax(dp[p][i-1][j],dp[p^1][i-1][j]),dp[p^1][i-1][j]=0;
			p^=1;
		}
		f(j,0,X){
			dp[p][i][j]=dp[p][i-1][j];
			dp[p^1][i][j]=dp[p^1][i-1][j];
			if(j>=w[i].p){
				updmax(dp[p][i][j],dp[p][i-1][j-w[i].p]+w[i].u);
				updmax(dp[p][i][j],dp[p^1][i-1][j-w[i].p]+w[i].u+K);
			}
			updmax(ans,dp[p][i][j]);
			updmax(ans,dp[p^1][i][j]);
		}
	}
	cout<<ans<<endl;
}
signed main(){
#ifndef XQZ
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
#endif
#ifdef NXD
	int t=0;cin>>t;while(t--)
#endif
		gs();
	return 0;
}

Submission Info

Judge Result