This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define sz(a) ((int)a.size())
using namespace std;
const int N=51000,bal=20,inf=(1LL<<60);
signed main(){
int n;
cin>>n;
vector<int> c,f,v;
vector<int> index;
for(int i=0;i<n;i++){
int ci,fi,vi; cin>>ci>>fi>>vi;
c.pb(ci); f.pb(fi); v.pb(vi*-1);
index.push_back(i);
}
int m;
cin>>m;
for(int i=0;i<m;i++){
int ci,fi,vi; cin>>ci>>fi>>vi;
index.push_back(sz(c));
c.pb(ci*-1);f.pb(fi); v.pb(vi);
}
sort(index.begin(),index.end(),[&](int a,int b){if(f[a]==f[b]) return c[a]>c[b]; return f[a]>f[b]; });
vector<int> dp(N,-inf);
dp[0]=0;
int answer=0;
for(int i:index){
vector<int> ndp=dp;
for(int value=0;value<N;value++)
if(value-c[i]<N&&value-c[i]>=0)
ndp[value]=max(dp[value-c[i]]+v[i],ndp[value]);
dp=ndp;
for(int value=0;value<N;value++)
answer=max(answer,dp[value]);
}
cout<<answer;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |