Submission #1091571

#TimeUsernameProblemLanguageResultExecution timeMemory
1091571LmaoLmaoCloud Computing (CEOI18_clo)C++14
100 / 100
414 ms1500 KiB
#include <bits/stdc++.h> #define fi first #define se second #define ll long long using namespace std; using ii=pair<int,int>; using aa=array<ll,3>; ll dp[100005]; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); int n; cin >> n; vector<aa> a; int sum=0; for(int i=1;i<=n;i++) { aa x; cin >> x[1] >> x[0] >> x[2]; sum+=x[1]; x[2]=-x[2]; a.push_back(x); } int m; cin >> m; for(int i=1;i<=m;i++) { aa x; cin >> x[1] >> x[0] >> x[2]; x[1]=-x[1]; a.push_back(x); } for(int i=0;i<=sum;i++) dp[i]=-1e18; dp[0]=0; sort(a.begin(),a.end(),greater<>()); ll ans=0; for(aa x:a) { if(x[1]<0) { for(int i=0;i<=sum;i++) { if(i+x[1]>=0 && i+x[1]<=sum) { dp[i+x[1]]=max(dp[i+x[1]],dp[i]+x[2]); ans=max(ans,dp[i+x[1]]); } } } else { for(int i=sum;i>=0;i--) { if(i+x[1]>=0 && i+x[1]<=sum) { dp[i+x[1]]=max(dp[i+x[1]],dp[i]+x[2]); ans=max(ans,dp[i+x[1]]); } } } } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...