Submission #1261438

#TimeUsernameProblemLanguageResultExecution timeMemory
1261438doqCloud Computing (CEOI18_clo)C++20
100 / 100
204 ms1096 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define fo(i,a,b) for(int i = (a); i <= (b); i++) #define fod(i,a,b) for(int i = (a); i >= (b); i--) #define fi first #define se second #define pii pair<int,int> #define pb push_back #define ll long long const int N = 2e3 + 5; const int inf = 1e15; int n, m; struct pp { int fi, se, th; } b[N * 2]; int nn; bool cmp(pp a, pp b) { if(a.se != b.se) return a.se > b.se; return a.th < b.th; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("1.inp", "r", stdin); // freopen("1.out", "w", stdout); cin >> n; fo(i, 1, n){ int x, y, w; cin >> x >> y >> w; b[i] = {x, y, -w}; } cin >> m; nn = n + m; fo(i, 1, m) { int x, y, z; cin >> x >> y >> z; b[i + n] = {-x, y, z}; } sort(b + 1, b + nn + 1, cmp); const int up = 2000 * 50; vector<int> f(up + 5, -inf); f[0] = 0; int sum = 0; fo(i, 1, nn) { if(b[i].fi > 0) { fod(j, sum, 0) if(j + b[i].fi <= up) f[j + b[i].fi] = max(f[j + b[i].fi], f[j] + b[i].th); sum += b[i].fi; } else { int tmp = -b[i].fi; fo(j, tmp, sum) { int now = j - tmp; f[now] = max(f[now], f[j] + b[i].th); } } } int res = 0; fo(i, 0, sum) res = max(res, f[i]); cout << res; }
#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...