제출 #1196680

#제출 시각아이디문제언어결과실행 시간메모리
1196680iamhereforfunCloud Computing (CEOI18_clo)C++20
54 / 100
158 ms1352 KiB
// IamHereForFun // #include <bits/stdc++.h> using namespace std; #define LSOne(S) ((S) & -(S)) const int N = 1e5 + 5; const int M = 45e5 + 5; const int K = 4; const int LG = 20; const long long INF = -1e18; const int MOD = 1e9 + 7; const int B = 50; struct Obj { int c, f, v, t; Obj(int x, int y, int z, int a) { c = x; f = y; v = z; t = a; } inline bool operator<(Obj a) { if (a.f == f) { return a.t < t; } return a.f < f; } void print() { cout << c << " " << f << " " << v << " " << t << "\n"; } }; int n, m, num = 0; long long dp[N]; vector<Obj> vec; void solve() { cin >> n; for (int x = 0; x < n; x++) { int a, b, c; cin >> a >> b >> c; vec.push_back({a, b, c, 0}); } cin >> m; for (int x = 0; x < m; x++) { int a, b, c; cin >> a >> b >> c; vec.push_back({a, b, c, 1}); } for (int x = 0; x < N; x++) { dp[x] = INF; } dp[0] = 0; sort(vec.begin(), vec.end()); for (Obj o : vec) { // cout << o.c << " " << o.f << " " << o.v << " " << o.t << "\n"; // continue; if (o.t == 1) { for (int x = o.c; x <= num; x++) { dp[x - o.c] = max(dp[x - o.c], dp[x] + o.v); } } else { for (int x = num; x >= 0; x--) { dp[x + o.c] = max(dp[x + o.c], dp[x] - o.v); } num += o.c; } // cout << num << "\n"; // for (int x = 0; x <= num; x++) // { // cout << dp[x] << " " << x << "\n"; // } } cout << *max_element(dp, dp + N); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; // cin >> t; for (int x = 1; x <= t; x++) { solve(); } 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...