oj.uz

Submission #209681

# Submission time Handle Problem Language Result Execution time Memory
209681 2020-03-15T06:13:22 Z maomao90 Visiting Singapore (NOI20_visitingsingapore) C++14
23 / 100
 326 ms 262148 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1784 KB Output is correct
2 Correct 125 ms 37748 KB Output is correct
3 Correct 7 ms 1912 KB Output is correct
4 Correct 8 ms 4728 KB Output is correct
5 Correct 6 ms 2168 KB Output is correct
6 Correct 36 ms 12920 KB Output is correct
7 Correct 7 ms 1660 KB Output is correct
8 Correct 16 ms 5112 KB Output is correct
9 Correct 69 ms 22392 KB Output is correct
10 Correct 166 ms 44024 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 888 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 37 ms 10744 KB Output is correct
4 Correct 7 ms 1016 KB Output is correct
5 Correct 14 ms 3832 KB Output is correct
6 Correct 66 ms 21624 KB Output is correct
7 Correct 70 ms 21240 KB Output is correct
8 Correct 97 ms 31096 KB Output is correct
9 Correct 15 ms 4216 KB Output is correct
10 Correct 157 ms 44024 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 106744 KB Output is correct
2 Correct 134 ms 49400 KB Output is correct
3 Runtime error 145 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 106744 KB Output is correct
2 Correct 134 ms 49400 KB Output is correct
3 Runtime error 145 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 106744 KB Output is correct
2 Correct 134 ms 49400 KB Output is correct
3 Runtime error 145 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 632 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 888 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 5 ms 888 KB Output is correct
10 Correct 5 ms 1144 KB Output is correct
11 Correct 6 ms 1144 KB Output is correct
12 Correct 5 ms 1144 KB Output is correct
13 Correct 5 ms 1144 KB Output is correct
14 Correct 6 ms 1144 KB Output is correct
15 Correct 6 ms 1144 KB Output is correct

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1784 KB Output is correct
2 Correct 125 ms 37748 KB Output is correct
3 Correct 7 ms 1912 KB Output is correct
4 Correct 8 ms 4728 KB Output is correct
5 Correct 6 ms 2168 KB Output is correct
6 Correct 36 ms 12920 KB Output is correct
7 Correct 7 ms 1660 KB Output is correct
8 Correct 16 ms 5112 KB Output is correct
9 Correct 69 ms 22392 KB Output is correct
10 Correct 166 ms 44024 KB Output is correct
11 Correct 6 ms 888 KB Output is correct
12 Correct 5 ms 632 KB Output is correct
13 Correct 37 ms 10744 KB Output is correct
14 Correct 7 ms 1016 KB Output is correct
15 Correct 14 ms 3832 KB Output is correct
16 Correct 66 ms 21624 KB Output is correct
17 Correct 70 ms 21240 KB Output is correct
18 Correct 97 ms 31096 KB Output is correct
19 Correct 15 ms 4216 KB Output is correct
20 Correct 157 ms 44024 KB Output is correct
21 Correct 326 ms 106744 KB Output is correct
22 Correct 134 ms 49400 KB Output is correct
23 Runtime error 145 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Halted 0 ms 0 KB -