Submission #1226316

#TimeUsernameProblemLanguageResultExecution timeMemory
1226316radodododoCloud Computing (CEOI18_clo)C++20
0 / 100
217 ms327680 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; struct node { long long c, f, w, tip; node(long long c = 0, long long f = 0, long long w = 0, long long tip = 0) { this->c = c; this->f = f; this->w = w; this->tip = tip; } }; bool cmp(node a, node b) { return (a.f < b.f) || (a.f == b.f && a.tip < b.tip); } int main() { long long n; cin >> n; vector<node> v(n); for (long long i = 0; i < n; i++) { cin >> v[i].c >> v[i].f >> v[i].w; v[i].tip = 1; } long long m; cin >> m; for (long long i = 0; i < m; i++) { long long c, f, w; cin >> c >> f >> w; v.push_back(node(c, f, w, 0)); } long long siz = 100000 + 52; long long inf = 1e18; sort(v.begin(), v.end(), cmp); reverse(v.begin(), v.end()); vector<vector<long long>> dp(v.size() + 1, vector<long long>(siz, -inf)); dp[0][0] = 0; long long ans = 0; for (long long i = 0; i < v.size(); i++) { dp[i + 1] = dp[i]; for (long long x = 0; x < siz; x++) { if (v[i].tip == 1 && dp[i][max(x - v[i].c, (long long)0)] != -inf) { dp[i + 1][x] = max(dp[i][x], dp[i][max(x - v[i].c, (long long)0)] - v[i].w); } if (v[i].tip == 0 && x + v[i].c < siz && dp[i][x + v[i].c] != -inf) { dp[i + 1][x] = max(dp[i][x], dp[i][x + v[i].c] + v[i].w); } ans = max(ans, dp[i + 1][x]); } } 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...