oj.uz

Submission #132804

# Submission time Handle Problem Language Result Execution time Memory
132804 2019-07-19T15:22:21 Z SamAnd Cloud Computing (CEOI18_clo) C++17
100 / 100
 1243 ms 2296 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 2003;
const long long INF = 100005000000009;
struct ban
{
    bool z;
    int q, x, g;
};
bool operator<(const ban& a, const ban& b)
{
    if (a.x < b.x)
        return true;
    if (a.x > b.x)
        return false;
    return a.z < b.z;
}

int n, m;
ban a[N + N];

long long dp[N * 55];
long long ndp[N * 55];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        a[i].z = true;
        scanf("%d%d%d", &a[i].q, &a[i].x, &a[i].g);
    }
    scanf("%d", &m);
    for (int i = n + 1; i <= n + m; ++i)
    {
        a[i].z = false;
        scanf("%d%d%d", &a[i].q, &a[i].x, &a[i].g);
    }
    sort(a + 1, a + n + m + 1);
    for (int i = 1; i <= n * 50; ++i)
        dp[i] = -INF;
    for (int i = n + m; i >= 1; --i)
    {
        memset(ndp, -INF, sizeof ndp);
        if (a[i].z)
        {
            for (int j = 0; j <= n * 50; ++j)
            {
                ndp[j] = max(ndp[j], dp[j]);
                if (j + a[i].q <= n * 50)
                    ndp[j + a[i].q] = max(ndp[j + a[i].q], dp[j] - a[i].g);
            }
        }
        else
        {
            for (int j = 0; j <= n * 50; ++j)
            {
                ndp[j] = max(ndp[j], dp[j]);
                if (j - a[i].q >= 0)
                    ndp[j - a[i].q] = max(ndp[j - a[i].q], dp[j] + a[i].g);
            }
        }
        memcpy(dp, ndp, sizeof ndp);
    }
    long long ans = 0;
    for (int j = 0; j <= n * 50; ++j)
        ans = max(ans, dp[j]);
    cout << ans << endl;
    return 0;
}

Compilation message

clo.cpp: In function 'int main()':
clo.cpp:43:21: warning: overflow in implicit constant conversion [-Woverflow]
         memset(ndp, -INF, sizeof ndp);
                     ^~~~
clo.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
clo.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &a[i].q, &a[i].x, &a[i].g);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
clo.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &m);
     ~~~~~^~~~~~~~~~
clo.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &a[i].q, &a[i].x, &a[i].g);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2040 KB Output is correct
2 Correct 4 ms 2040 KB Output is correct
3 Correct 18 ms 2040 KB Output is correct
4 Correct 30 ms 2040 KB Output is correct
5 Correct 251 ms 2040 KB Output is correct
6 Correct 252 ms 2168 KB Output is correct
7 Correct 288 ms 2168 KB Output is correct
8 Correct 264 ms 2232 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2040 KB Output is correct
2 Correct 8 ms 2012 KB Output is correct
3 Correct 19 ms 2044 KB Output is correct
4 Correct 18 ms 2140 KB Output is correct
5 Correct 197 ms 2124 KB Output is correct
6 Correct 200 ms 2168 KB Output is correct
7 Correct 621 ms 2168 KB Output is correct
8 Correct 630 ms 2168 KB Output is correct
9 Correct 591 ms 2296 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2040 KB Output is correct
2 Correct 7 ms 2040 KB Output is correct
3 Correct 28 ms 2088 KB Output is correct
4 Correct 29 ms 2040 KB Output is correct
5 Correct 57 ms 2040 KB Output is correct
6 Correct 58 ms 2100 KB Output is correct
7 Correct 80 ms 2040 KB Output is correct
8 Correct 79 ms 2168 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2040 KB Output is correct
2 Correct 6 ms 2196 KB Output is correct
3 Correct 399 ms 2140 KB Output is correct
4 Correct 238 ms 2168 KB Output is correct
5 Correct 1169 ms 2168 KB Output is correct
6 Correct 1232 ms 2296 KB Output is correct
7 Correct 1226 ms 2168 KB Output is correct
8 Correct 1241 ms 2188 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2040 KB Output is correct
2 Correct 25 ms 2128 KB Output is correct
3 Correct 160 ms 2108 KB Output is correct
4 Correct 410 ms 2140 KB Output is correct
5 Correct 1219 ms 2268 KB Output is correct
6 Correct 1223 ms 2172 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2040 KB Output is correct
2 Correct 4 ms 2040 KB Output is correct
3 Correct 18 ms 2040 KB Output is correct
4 Correct 30 ms 2040 KB Output is correct
5 Correct 251 ms 2040 KB Output is correct
6 Correct 252 ms 2168 KB Output is correct
7 Correct 288 ms 2168 KB Output is correct
8 Correct 264 ms 2232 KB Output is correct
9 Correct 4 ms 2040 KB Output is correct
10 Correct 8 ms 2012 KB Output is correct
11 Correct 19 ms 2044 KB Output is correct
12 Correct 18 ms 2140 KB Output is correct
13 Correct 197 ms 2124 KB Output is correct
14 Correct 200 ms 2168 KB Output is correct
15 Correct 621 ms 2168 KB Output is correct
16 Correct 630 ms 2168 KB Output is correct
17 Correct 591 ms 2296 KB Output is correct
18 Correct 7 ms 2040 KB Output is correct
19 Correct 7 ms 2040 KB Output is correct
20 Correct 28 ms 2088 KB Output is correct
21 Correct 29 ms 2040 KB Output is correct
22 Correct 57 ms 2040 KB Output is correct
23 Correct 58 ms 2100 KB Output is correct
24 Correct 80 ms 2040 KB Output is correct
25 Correct 79 ms 2168 KB Output is correct
26 Correct 5 ms 2040 KB Output is correct
27 Correct 6 ms 2196 KB Output is correct
28 Correct 399 ms 2140 KB Output is correct
29 Correct 238 ms 2168 KB Output is correct
30 Correct 1169 ms 2168 KB Output is correct
31 Correct 1232 ms 2296 KB Output is correct
32 Correct 1226 ms 2168 KB Output is correct
33 Correct 1241 ms 2188 KB Output is correct
34 Correct 4 ms 2040 KB Output is correct
35 Correct 25 ms 2128 KB Output is correct
36 Correct 160 ms 2108 KB Output is correct
37 Correct 410 ms 2140 KB Output is correct
38 Correct 1219 ms 2268 KB Output is correct
39 Correct 1223 ms 2172 KB Output is correct
40 Correct 179 ms 2120 KB Output is correct
41 Correct 377 ms 2168 KB Output is correct
42 Correct 823 ms 2296 KB Output is correct
43 Correct 1230 ms 2192 KB Output is correct
44 Correct 1243 ms 2108 KB Output is correct
45 Correct 1226 ms 2236 KB Output is correct
46 Correct 456 ms 2172 KB Output is correct
47 Correct 820 ms 2268 KB Output is correct
48 Correct 825 ms 2296 KB Output is correct