| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 762261 | NeroZein | 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"
#define int long long
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif
struct sth {
int c, f, v;
};
const int N = 4003;
const int MX = 2000 * 50 + 1;
sth a[N];
int dp[N][MX];
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
int c, f, v;
cin >> c >> f >> v;
a[i] = {c, f, -v};
}
int m;
cin >> m;
for (int i = 1; i <= m; ++i) {
int c, f, v;
cin >> c >> f >> v;
a[i + n] = {-c, f, v};
}
sort(a + 1, a + n + m + 1, [&](const sth& x, const sth& y) {
return (x.f == y.f ? x.c > y.c : x.f > y.f);
});
for (int i = 0; i <= n + m; ++i) {
fill(dp[i], dp[i] + MX, -1e9);
}
dp[0][0] = 0;
for (int i = 1; i <= n + m; ++i) {
auto [c, f, v] = a[i];
for (int j = 0; j < MX; ++j) {
dp[i][j] = dp[i - 1][j];
}
if (c < 0) {//order
for (int j = 0; j - c < MX; ++j) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - c] + v);
}
} else {
for (int j = c; j < MX; ++j) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - c] + v);
}
}
}
int ans = 0;
for (int i = 0; i < MX; ++i) {
ans = max(ans, dp[n + m][i]);
}
cout << ans << '\n';
return 0;
}