| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 972866 | Gajowy | Cloud Computing (CEOI18_clo) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
};
struct order {
int c, f, 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';
}