# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
997147 | daffuwu | Cloud Computing (CEOI18_clo) | C++14 | 183 ms | 3228 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 fr first
#define sc second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long n, m, dp1[2][100069], dp2[2][100069], c, f, v, ps1, ps2, ans, mn;
int main()
{
long long i, sm;
// for (sm=1; sm<=100000) dp1[0][sm] = 0;
scanf("%lld", &n);
for (i=1; i<=n; i++)
{
scanf("%lld%lld%lld", &c, &f, &v);
for (sm=0; sm<=ps1+c; sm++)
{
if (sm<=ps1) dp1[i%2][sm] = dp1[(i+1)%2][sm];
else dp1[i%2][sm] = 1e15;
if (sm>=c) dp1[i%2][sm] = min(dp1[i%2][sm], dp1[(i+1)%2][sm-c]+v);
}
ps1 += c;
}
scanf("%lld", &m);
for (i=1; i<=m; i++)
{
scanf("%lld%lld%lld", &c, &f, &v);
for (sm=0; sm<=ps2+c; sm++)
{
if (sm<=ps2) dp2[i%2][sm] = dp2[(i+1)%2][sm];
else dp2[i%2][sm] = -1e15;
if (sm>=c) dp2[i%2][sm] = max(dp2[i%2][sm], dp2[(i+1)%2][sm-c]+v);
}
ps2 += c;
}
for (sm=ps1-1; sm>=0; sm--) dp1[n%2][sm] = min(dp1[n%2][sm], dp1[n%2][sm+1]);
mn = min(ps1, ps2);
for (sm=0; sm<=mn; sm++)
{
// printf("dp1[%lld][%lld] = %lld dp2[%lld][%lld] = %lld\n", n, sm, dp1[n%2][sm], m, sm, dp2[m%2][sm]);
ans = max(ans, dp2[m%2][sm]-dp1[n%2][sm]);
}
printf("%lld\n", 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... |