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>
using namespace std;
typedef long long ll;
struct str{
ll c, f, v, type;
} niz[4005];
bool cmp(str a, str b){
if(a.f < b.f) return 0;
if(a.f > b.f) return 1;
return a.type > b.type;
}
ll dp[100005];
ll dpp[100005];
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
int n;
cin >> n;
for(int i=1; i<=n; i++){
cin >> niz[i].c >> niz[i].f >> niz[i].v;
niz[i].type = 1;
}
int m;
cin >> m;
for(int i=1; i<=m; i++){
cin >> niz[i+n].c >> niz[i+n].f >> niz[i+n].v;
niz[i+n].type = -1;
}
sort(niz+1, niz+1+n+m, cmp);
ll sm = 0, smp = 0;
for(int i=1; i<=1e5; i++) dpp[i] = -1e15;
for(int i=1; i<=n+m; i++){
sm += max(niz[i].type*niz[i].c, 0LL);
for(int j=0; j<=sm; j++){
dp[j] = dpp[j];
if(j-niz[i].type*niz[i].c >= 0LL && j-niz[i].type*niz[i].c <= smp) dp[j] = max(dp[j], dpp[j-niz[i].type*niz[i].c] - niz[i].type*niz[i].v);
}
for(int j=0; j<=sm; j++) dpp[j] = dp[j];
smp = sm;
}
ll mx = 0;
for(int j=0; j<=sm; j++) mx = max(mx, dp[j]);
cout << mx;
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... |