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 st first
#define nd second
using namespace std;
const int N=200005,mod=1000000007;
int n,m,k,l,x,h[N];
long long dp[N],nxt[N];
vector<int>v[N];
pair<pair<int,bool>,pair<int,int> > arr[N];
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
cin >> n;
for(int i=1;i<=n;i++){
cin >> arr[i].nd.st >> arr[i].st.st >> arr[i].nd.nd;
arr[i].st.nd=1;
}
cin >> m;
for(int i=1;i<=m;i++){
cin >> arr[n+i].nd.st >> arr[n+i].st.st >> arr[n+i].nd.nd;
arr[n+i].st.nd=0;
}
sort(arr+1,arr+n+m+1);
reverse(arr+1,arr+n+m+1);
long long sum=0;
for(int i=1;i<N;i++)dp[i]=-1e18;
for(int i=1;i<=n+m;i++){
if(arr[i].st.nd==1){
sum+=arr[i].nd.st;
for(int j=0;j<=sum;j++){
nxt[j]=dp[j];
if(j>=arr[i].nd.st){
nxt[j]=max(nxt[j],dp[j-arr[i].nd.st]-arr[i].nd.nd);
}
}
}
else{
for(int j=sum;j>=0;j--){
nxt[j]=dp[j];
if(j+arr[i].nd.st<=sum){
nxt[j]=max(nxt[j],dp[j+arr[i].nd.st]+arr[i].nd.nd);
}
}
}
for(int j=0;j<=sum;j++){
dp[j]=nxt[j];
}
}
long long ans=0;
for(int i=0;i<=sum;i++){
ans=max(ans,dp[i]);
}
cout << ans << endl;
}
# | 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... |