제출 #972871

#제출 시각아이디문제언어결과실행 시간메모리
972871GajowyCloud Computing (CEOI18_clo)C++17
18 / 100
868 ms2256 KiB
#include <bits/stdc++.h> using namespace std; #define fwd(i, a, n) for (int i = (a); i < (n); i ++) #define rep(i, n) fwd(i, 0, n) #define all(X) begin(X), end(X) #define sz(X) ((int)X.size()) #define st first #define nd second #define vi vector<int> #define pii pair<int, int> #define ll long long #define vll vector<long long> #ifdef LOC auto &operator<<(auto &out, pair<auto, auto> a) { return out << "(" << a.st << ", " << a.nd << ")"; } auto &operator<<(auto &out, auto a) { out << "{"; for (auto b : a) out << b << ", "; return out << "}"; } void dump(auto... x) { ((cerr << x << ", "), ...) << '\n'; } #define debug(x...) cerr << "[" #x "]: ", dump(x) #else #define debug(...) 0 #endif const int maxN = 2000 + 10; const int maxC = 50; const ll inf = 1e18; struct computer { int c, f, v; computer() {} computer(int c, int f, int v) : c(c), f(f), v(v) {} }; struct order { int c, f, v; order() {} order(int c, int f, int v) : c(c), f(f), v(v) {} }; computer comp[maxN]; order ord[maxN]; vector<vll> dp, tmp; void fix(int cid, int m) { rep(i, m) { rep(j, maxC + 1) { dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]); if (ord[i + 1].c <= j && ord[i + 1].f <= comp[cid].f) { dp[i + 1][j - ord[i + 1].c] = max( dp[i + 1][j - ord[i + 1].c], dp[i][j] + ord[i + 1].v ); } } } } void ext(int cid, int m) { tmp = dp; rep(i, m + 1) rep(j, maxC + 1) { int s = min(maxC, j + comp[cid].c); tmp[i][s] = max(tmp[i][s], dp[i][j] - comp[cid].v); } swap(tmp, dp); } int32_t main() { ios_base::sync_with_stdio(0), cin.tie(0); int n; cin >> n; for (int i = 1; i <= n; i ++) { int c, f, v; cin >> c >> f >> v; comp[i] = computer(c, f, v); } int m; cin >> m; for (int i = 1; i <= m; i ++) { int c, f, v; cin >> c >> f >> v; ord[i] = order(c, f, v); } sort(comp + 1, comp + n + 1, [&](auto &a, auto &b) { return a.f > b.f; }); sort(ord + 1, ord + m + 1, [&](auto &a, auto &b) { return a.f > b.f; }); dp.resize(m + 1, vll(maxC + 1, -inf)); tmp = dp; dp[0][0] = 0; for (int i = 1; i <= n; i ++) { ext(i, m); fix(i, m); } cout << *max_element(all(dp.back())) << '\n'; }
#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...