Submission #209679

#TimeUsernameProblemLanguageResultExecution timeMemory
209679maomao90Visiting Singapore (NOI20_visitingsingapore)C++14
23 / 100
334 ms262148 KiB
#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;

#define INF 1000000000

//#define TC

int K, n, m, A, B;
int V[1005], S[5005], T[5005];
int ans = -INF;

//dp(s, t, state) returns the maximum happiness from S[s to n-1] and T[t to n-1];
//state = 0 means that S[s-1] and T[t-1] were both not attended;
//state = 1 means that S[s-1] was attended but T[t-1] was not attended;
//state = 2 means that S[s-1] was not attended but T[t-1] was attended;
//state = 3 means that S[s-1] and T[t-1] were both attended;
//start = 0 means that he still have not started his trip;
//start = 1 means that his trip already started;
int memo[5005][5005][5][2];
int dp(int s, int t, int state, int start)
{
    if (t >= m) return 0;
    if (s >= n)
    {
        if (state == 1 || state == 3 || start == 0) return A + B * (m - t);
        else return B * (m - t);
    }
    if (memo[s][t][state][start] != INF) return memo[s][t][state][start];
    if (start == 0)
    {
        if (state == 0)
        {
            memo[s][t][state][start] = max(dp(s + 1, t, 0, 0), dp(s, t + 1, 0, 0) + B);
        }
        else if (state == 1)
        {
            memo[s][t][state][start] = max(dp(s + 1, t, 0, 0), dp(s, t + 1, 1, 0) + B);
        }
        else if (state == 2)
        {
            memo[s][t][state][start] = max(dp(s + 1, t, 2, 0), dp(s, t + 1, 0, 0) + A + B);
        }
        else if (state == 3)
        {
            memo[s][t][state][start] = max(dp(s + 1, t, 2, 0), dp(s, t + 1, 1, 0) + A + B);
        }
    }
    else
    {
        if (state == 0)
        {
            memo[s][t][state][start] = max(dp(s + 1, t, 0, 1) + B, dp(s, t + 1, 0, 1) + B);
        }
        else if (state == 1)
        {
            memo[s][t][state][start] = max(dp(s + 1, t, 0, 1) + A + B, dp(s, t + 1, 1, 1) + B);
        }
        else if (state == 2)
        {
            memo[s][t][state][start] = max(dp(s + 1, t, 2, 1) + B, dp(s, t + 1, 0, 1) + A + B);
        }
        else if (state == 3)
        {
            memo[s][t][state][start] = max(dp(s + 1, t, 2, 1) + A + B, dp(s, t + 1, 1, 1) + A + B);
        }
    }
    if (S[s] == T[t]) memo[s][t][state][start] = max(memo[s][t][state][start], dp(s + 1, t + 1, 3, 1) + V[S[s]]);
    return memo[s][t][state][start];
}

int main()
{
    #ifdef TC
    for (int i = 1; i <= 100; i++)
    {
        char temp[5];
        sprintf(temp, "%03d", i);
        string filein, fileout;
        filein = string(temp), fileout = string(temp);
        filein = "tests/" + filein + ".in";
        fileout = "out/" + fileout + ".out";
        freopen(filein.c_str(), "r", stdin);
        freopen(fileout.c_str(), "w", stdout);
        scanf("%d%d%d%d%d", &K, &n, &m, &A, &B);
        for (int i = 1; i <= K; i++) scanf("%d", &V[i]);
        for (int i = 0; i < n; i++) scanf("%d", &S[i]);
        for (int i = 0; i < m; i++) scanf("%d", &T[i]);
        for (int i = 0; i < n + 5; i++) for (int j = 0; j < m + 5; j++) for (int k = 0; k < 5; k++) for (int l = 0; l < 2; l++) memo[i][j][k][l] = INF;
        printf("%d\n", dp(0, 0, 3, 0));
        fclose(stdin);
        fclose(stdout);
    }
    #else
    scanf("%d%d%d%d%d", &K, &n, &m, &A, &B);
    for (int i = 1; i <= K; i++) scanf("%d", &V[i]);
    for (int i = 0; i < n; i++) scanf("%d", &S[i]);
    for (int i = 0; i < m; i++) scanf("%d", &T[i]);
    for (int i = 0; i < n + 5; i++) for (int j = 0; j < m + 5; j++) for (int k = 0; k < 5; k++) for (int l = 0; l < 2; l++) memo[i][j][k][l] = INF;
    printf("%d\n", dp(0, 0, 3, 0));
    return 0;
    #endif // TC
}

/*
Sample 4:
4 8 4 0 -3
1 2 3 4
3 1 2 1 1 4 1 1
1 2 3 4

Sample 5:
4 8 4 -3 0
1 2 3 4
3 1 2 1 1 4 1 1
1 2 3 4

Sample 6:
6 10 6 -2 -1
1 2 3 4 5 6
3 1 5 2 6 1 5 1 1 4
1 2 3 4 5 6
*/

Compilation message (stderr)

VisitingSingapore.cpp: In function 'int main()':
VisitingSingapore.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d%d", &K, &n, &m, &A, &B);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
VisitingSingapore.cpp:98:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= K; i++) scanf("%d", &V[i]);
                                  ~~~~~^~~~~~~~~~~~~
VisitingSingapore.cpp:99:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 0; i < n; i++) scanf("%d", &S[i]);
                                 ~~~~~^~~~~~~~~~~~~
VisitingSingapore.cpp:100:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 0; i < m; i++) scanf("%d", &T[i]);
                                 ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...