Submission #467942

#TimeUsernameProblemLanguageResultExecution timeMemory
467942ivan_tudorCloud Computing (CEOI18_clo)C++14
100 / 100
492 ms1476 KiB
#include<bits/stdc++.h> using namespace std; const int N = 2005; const int NM = N * 50; long long dp[NM]; struct requesth{ int c, f, v; bool tip; }; bool cmp(requesth a, requesth b){ if(a.f == b.f) return a.tip < b.tip; return a.f > b.f; } vector<requesth> v; int main() { //freopen(".in","r",stdin); ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); long long sum = 0; int n, m; cin>>n; for(int i =1; i<=n; i++){ int c, f, val; cin>>c>>f>>val; sum -= 1LL * val; v.push_back({c, f, val, false}); v.push_back({c, f, val, true}); } cin>>m; for(int i =1; i<=m; i++ ){ int c, f, val; cin>>c>>f>>val; v.push_back({c, f, val, true}); } sort(v.begin(), v.end(), cmp); for(int i = 0; i < NM; i++){ dp[i] = LLONG_MIN; } dp[0] = sum; long long csum = 0; for(auto x: v){ if(x.tip == 0){ csum += x.c; for(int i = csum; i >= 0; i--){ if(i - x.c >= 0) dp[i] = dp[i - x.c]; else dp[i] = LLONG_MIN; } } if(x.tip == 1){ for(int i = 0; i<= csum - x.c; i++){ dp[i] = max(dp[i], dp[i + x.c] + 1LL * x.v); } } } long long ans = 0; for(int i = 0; i < NM; i++) ans = max(ans, dp[i]); cout<<ans; return 0; }
#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...