# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
637836 | Neos | Cloud Computing (CEOI18_clo) | C++14 | 1689 ms | 4076 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 ll long long
#define ar array
template <class T>
bool minimize(T &a, const T &b) {
if(a > b) {a = b; return 1;}
return 0;
}
template <class T>
bool maximize(T &a, const T &b) {
if(a < b) {a = b; return 1;}
return 0;
}
const int N = 4e3 + 7, M = 50 + 7, MOD = 1e9 + 7, oo = (1 << 30);
int n, m;
ll dp[N * M + M], prv[N * M + M];
struct item {
int c, f, v;
item() {}
item(int c, int f, int v):
c(c), f(f), v(v) {}
bool operator<(const item &other) const {
return f > other.f;
}
} a[N];
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
if (fopen("test.inp", "r"))
freopen("test.inp", "r", stdin);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].c >> a[i].f >> a[i].v;
a[i].v = -a[i].v;
}
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> a[i + n].c >> a[i + n].f >> a[i + n].v;
a[i + n].c = -a[i + n].c;
}
sort(a + 1, a + n + m + 1);
fill(prv, prv + N * M + M + 1, -oo);
prv[M] = 0;
int st = 0;
while (a[st + 1].c < 0) ++st;
for (int i = st; i < n + m; i++) {
fill(dp, dp + N * M + M + 1, -oo);
for (int j = 0; j <= 50 * n; j++) if (prv[j + M] != -oo) {
// choose
if (j + a[i + 1].c <= 50 * n) {
maximize(dp[M + j + a[i + 1].c], prv[j + M] + a[i + 1].v);
}
// not choose
maximize(dp[M + j], prv[j + M]);
}
swap(dp, prv);
}
ll ans = 0;
for (int i = 0; i <= 50 * n; i++) {
maximize(ans, prv[i + M]);
}
cout << ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |