Ang_QwQ @ 2022-08-13 20:38:35
#include<iostream>
using namespace std;
const int N=32001;
int sumv,m,v[N][4],p[N][4],f[N];
int cnt=0;
int sum(int l,int r){
int ans=0;
for(int i=l;i<=r;i++){
ans+=v[cnt][i];
}
return ans;
}
int score(int k){
return v[cnt][k]*p[cnt][k];
}
int main(){
std::ios::sync_with_stdio(false);
cin>>sumv>>m;
for(int i=1;i<=m;i++){
int a,b,q;
cin>>a>>b>>q;
if(q==0){
v[i][0]=a;
p[i][0]=b;
}
else{
if(v[q][1]==0){
v[q][1]=a;
p[q][1]=b;
}
else{
v[q][2]=a;
p[q][2]=b;
}
}
}
for(int i=1;i<=m;i++){
cnt=i;
// cout<<"QWQ"<<cnt<<endl;
for(int j=sumv;j>=0;j--){
if(f[j]>=sum(0,0)){ f[j]=max(f[j],f[j-sum(0,0)]+score(0));/*cout<<"qwq"<<f[j-sum(0,0)]<<" "<<score(0)<<" "<<j<<endl;*/}
if(f[j]>=sum(0,1)){ f[j]=max(f[j],f[j-sum(0,1)]+score(0)+score(1));}
if(f[j]>=sum(0,2)){ f[j]=max(f[j],f[j-sum(0,2)]+score(0)+score(1)+score(2));}
if(f[j]>=v[i][0]+v[i][2]){ f[j]=max(f[j],f[j-v[i][0]-v[i][2]]+score(0)+score(2));}
}
// cout<<sum(0,0)<<" "<<sum(0,1)<<" "<<sum(0,2)<<" "<<v[i][0]+v[i][2]<<endl;
cout<<score(0)<<" "<<score(0)+score(1)<<" "<<score(0)+score(1)+score(2)<<" "<<score(0)+score(2)<<endl;
}
// for(int i=1;i<=sumv;i++) cout<<f[i]<<" ";
cout<<f[sumv];
}
by _Glassy_Sky_ @ 2022-08-13 21:48:05
#include <iostream>
#define maxn 32005
using namespace std;
int n,m;
int v,p,q;
int main_item_w[maxn];
int main_item_c[maxn];
int annex_item_w[maxn][3];
int annex_item_c[maxn][3];
int f[maxn];
int main(){
cin >> n >> m;
for (int i=1;i<=m;i++){
cin >> v >> p >> q;
if (!q){
main_item_w[i] = v;
main_item_c[i] = v * p;
}
else{
annex_item_w[q][0]++;
annex_item_w[q][annex_item_w[q][0]] = v;
annex_item_c[q][annex_item_w[q][0]] = v * p;
}
}
for (int i=1;i<=m;i++)
for (int j=n;main_item_w[i]!=0 && j>=main_item_w[i];j--){
f[j] = max(f[j],f[j-main_item_w[i]]+main_item_c[i]);
if (j >= main_item_w[i] + annex_item_w[i][1])
f[j] = max(f[j],f[ j - main_item_w[i] - annex_item_w[i][1] ] + main_item_c[i] + annex_item_c[i][1]);
if (j >= main_item_w[i] + annex_item_w[i][2])
f[j] = max(f[j],f[ j - main_item_w[i] - annex_item_w[i][2] ] + main_item_c[i] + annex_item_c[i][2]);
if (j >= main_item_w[i] + annex_item_w[i][1] + annex_item_w[i][2])
f[j] = max(f[j],f[ j - main_item_w[i] - annex_item_w[i][1] - annex_item_w[i][2] ] + main_item_c[i] + annex_item_c[i][1] + annex_item_c[i][2]);
}
cout << f[n] << endl;
return 0;
}