oj.uz

Submission #54400

# Submission time Handle Problem Language Result Execution time Memory
54400 2018-07-03T10:16:22 Z bogdan10bos Semiexpress (JOI17_semiexpress) C++14
100 / 100
 221 ms 1248 KB 
#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef long long LL;

int N, M, K, A, B, C;
LL T;
int v[3005];
int dp[2][3005];

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d%d%d", &N, &M, &K);
    scanf("%d%d%d", &A, &B, &C);
    scanf("%lld", &T);
    for(int i = 1; i <= M; i++)
    {
        scanf("%d", &v[i]);
        v[i]--;
    }

    K -= M;
    for(int i = 1; i < M; i++)
    {
        for(int j = 0; j <= K; j++) dp[i & 1][j] = dp[(i - 1) & 1][j];

        int st = v[i];
        int dr = v[i + 1] - 1;
        LL t = T - 1LL * B * v[i];
        if(t < 0LL)   continue;

        LL rgt = st + LL(t / A);
        rgt = min(rgt, LL(dr));
        for(int j = 0; j <= K; j++)
            dp[i & 1][j] = max(dp[i & 1][j], dp[(i - 1) & 1][j] + int(rgt - st + 1));

        LL lft = rgt + 1;
        for(int j = 1; j <= K; j++)
        {
            if(lft > dr)    break;
            LL tt = t - 1LL * C * (lft - st);
            if(tt < 0)  break;
            LL rgt = lft + LL(tt / A);
            rgt = min(rgt, LL(dr));
            for(int k = j; k <= K; k++)
                dp[i & 1][k] = max(dp[i & 1][k], dp[(i - 1) & 1][k - j] + int(rgt - st + 1));
            lft = rgt + 1;
        }

    }
    int add = (T >= 1LL * B * v[M]);
    for(int i = 0; i <= K; i++)
        dp[M & 1][i] = dp[(M - 1) & 1][i] + add;
    for(int i = 1; i <= K; i++)
        dp[M & 1][i] = max(dp[M & 1][i], dp[M & 1][i - 1]);

    printf("%d\n", dp[M & 1][K] - 1);

    return 0;
}

Compilation message

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &M, &K);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &A, &B, &C);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &T);
     ~~~~~^~~~~~~~~~~~
semiexpress.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &v[i]);
         ~~~~~^~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 3 ms 416 KB Output is correct
4 Correct 2 ms 416 KB Output is correct
5 Correct 2 ms 532 KB Output is correct
6 Correct 2 ms 628 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 2 ms 632 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 3 ms 416 KB Output is correct
4 Correct 2 ms 416 KB Output is correct
5 Correct 2 ms 532 KB Output is correct
6 Correct 2 ms 628 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 3 ms 648 KB Output is correct
10 Correct 2 ms 744 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 2 ms 772 KB Output is correct
13 Correct 2 ms 852 KB Output is correct
14 Correct 2 ms 852 KB Output is correct
15 Correct 2 ms 872 KB Output is correct
16 Correct 2 ms 872 KB Output is correct
17 Correct 3 ms 880 KB Output is correct
18 Correct 2 ms 884 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 3 ms 416 KB Output is correct
4 Correct 2 ms 416 KB Output is correct
5 Correct 2 ms 532 KB Output is correct
6 Correct 2 ms 628 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 3 ms 648 KB Output is correct
10 Correct 2 ms 744 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 2 ms 772 KB Output is correct
13 Correct 2 ms 852 KB Output is correct
14 Correct 2 ms 852 KB Output is correct
15 Correct 2 ms 872 KB Output is correct
16 Correct 2 ms 872 KB Output is correct
17 Correct 3 ms 880 KB Output is correct
18 Correct 2 ms 884 KB Output is correct
19 Correct 3 ms 888 KB Output is correct
20 Correct 5 ms 908 KB Output is correct
21 Correct 2 ms 948 KB Output is correct
22 Correct 4 ms 968 KB Output is correct
23 Correct 221 ms 1028 KB Output is correct
24 Correct 2 ms 1028 KB Output is correct
25 Correct 2 ms 1040 KB Output is correct
26 Correct 2 ms 1060 KB Output is correct
27 Correct 2 ms 1208 KB Output is correct
28 Correct 3 ms 1208 KB Output is correct
29 Correct 129 ms 1208 KB Output is correct
30 Correct 214 ms 1248 KB Output is correct