Submission #54400

#	Time	Username	Problem	Language	Result	Execution time	Memory
54400		bogdan10bos	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	221 ms	1248 KiB

semiexpress

#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 (stderr)

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 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52