Submission #209681

#	Time	Username	Problem	Language	Result	Execution time	Memory
209681		maomao90	Visiting Singapore (NOI20_visitingsingapore)	C++14	23 / 100	326 ms	262148 KiB

VisitingSingapore

#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;

#define INF 1000000000

int K, n, m, A, B;
int V[1005], S[5005], T[5005];

//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()
{
    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 + 2; i++) for (int j = 0; j < m + 2; j++) for (int k = 0; k < 4; k++) for (int l = 0; l < 2; l++) memo[i][j][k][l] = INF;
    printf("%d\n", dp(0, 0, 3, 0));
    return 0;
}

/*
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:73: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:74: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:75: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:76: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]);
                                 ~~~~~^~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 6 / 6
• Subtask 3: 0 / 12
• Subtask 4: 0 / 7
• Subtask 5: 0 / 8
• Subtask 6: 13 / 13
• Subtask 7: 0 / 50