oj.uz

Submission #340853

# Submission time Handle Problem Language Result Execution time Memory
340853 2020-12-28T12:42:08 Z mihai145 Visiting Singapore (NOI20_visitingsingapore) C++14
23 / 100
 159 ms 262148 KB 
#include <iostream>

using namespace std;

const int INF = 1e9;

const int KMAX = 1000;
const int NMAX = 5000;

int K, N, M, A, B;
int dp[NMAX + 5][NMAX + 5][2][2];

int v[KMAX + 5], s[NMAX + 5], t[NMAX + 5];

int main()
{

    cin >> K >> N >> M >> A >> B;

    for(int i = 1; i <= K; i++)
        cin >> v[i];

    for(int i = 1; i <= N; i++)
        cin >> s[i];

    for(int i = 1; i <= M; i++)
        cin >> t[i];

    for(int i = 1; i <= N + 1; i++)
        for(int j = 0; j <= M; j++)
            for(int x = 0; x < 2; x++)
                for(int y = 0; y < 2; y++)
                    dp[i][j][x][y] = -INF;

    for(int i = 1; i <= N + 1; i++)
        dp[i][0][0][0] = 0;

    for(int i = 1; i <= N; i++)
    {
        if(i == 3)
            i++, i--;

        for(int j = 0; j <= M - 1; j++)
        {
            ///Skip concert
            dp[i][j + 1][0][1] = max(dp[i][j + 1][0][1], dp[i][j][0][0] + A + B);
            dp[i][j + 1][0][1] = max(dp[i][j + 1][0][1], dp[i][j][0][1] + B);
            dp[i][j + 1][1][1] = max(dp[i][j + 1][1][1], dp[i][j][1][0] + A + B);
            dp[i][j + 1][1][1] = max(dp[i][j + 1][1][1], dp[i][j][1][1] + B);

            ///Skip day
            dp[i + 1][j][1][0] = max(dp[i + 1][j][1][0], dp[i][j][0][0] + A + B);
            dp[i + 1][j][1][0] = max(dp[i + 1][j][1][0], dp[i][j][1][0] + B);
            dp[i + 1][j][1][1] = max(dp[i + 1][j][1][1], dp[i][j][0][1] + A + B);
            dp[i + 1][j][1][1] = max(dp[i + 1][j][1][1], dp[i][j][1][1] + B);

            ///Attend
            if(s[i] == t[j + 1])
            {
                dp[i + 1][j + 1][0][0] = max(dp[i + 1][j + 1][0][0], dp[i][j][0][0] + v[t[j + 1]]);
                dp[i + 1][j + 1][0][0] = max(dp[i + 1][j + 1][0][0], dp[i][j][1][0] + v[t[j + 1]]);
                dp[i + 1][j + 1][0][0] = max(dp[i + 1][j + 1][0][0], dp[i][j][0][1] + v[t[j + 1]]);
                dp[i + 1][j + 1][0][0] = max(dp[i + 1][j + 1][0][0], dp[i][j][1][1] + v[t[j + 1]]);
            }
        }
    }

    int res = A + M * B;
    for(int i = 1; i <= N + 1; i++)
        for(int x = 0; x < 2; x++)
            for(int y = 0; y < 2; y++)
                res = max(res, dp[i][M][x][y]);

    cout << res << '\n';

    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1516 KB Output is correct
2 Correct 20 ms 17516 KB Output is correct
3 Correct 1 ms 1516 KB Output is correct
4 Correct 3 ms 4076 KB Output is correct
5 Correct 1 ms 1900 KB Output is correct
6 Correct 7 ms 7296 KB Output is correct
7 Correct 1 ms 1260 KB Output is correct
8 Correct 3 ms 3308 KB Output is correct
9 Correct 16 ms 10988 KB Output is correct
10 Correct 26 ms 20204 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 5 ms 5228 KB Output is correct
4 Correct 1 ms 876 KB Output is correct
5 Correct 2 ms 2028 KB Output is correct
6 Correct 11 ms 10220 KB Output is correct
7 Correct 11 ms 9836 KB Output is correct
8 Correct 17 ms 14572 KB Output is correct
9 Correct 2 ms 2412 KB Output is correct
10 Correct 21 ms 20204 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 49024 KB Output is correct
2 Correct 23 ms 25964 KB Output is correct
3 Correct 138 ms 144280 KB Output is correct
4 Runtime error 159 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 49024 KB Output is correct
2 Correct 23 ms 25964 KB Output is correct
3 Correct 138 ms 144280 KB Output is correct
4 Runtime error 159 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 49024 KB Output is correct
2 Correct 23 ms 25964 KB Output is correct
3 Correct 138 ms 144280 KB Output is correct
4 Runtime error 159 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 1 ms 876 KB Output is correct
11 Correct 1 ms 876 KB Output is correct
12 Correct 1 ms 876 KB Output is correct
13 Correct 2 ms 876 KB Output is correct
14 Correct 1 ms 876 KB Output is correct
15 Correct 1 ms 876 KB Output is correct

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1516 KB Output is correct
2 Correct 20 ms 17516 KB Output is correct
3 Correct 1 ms 1516 KB Output is correct
4 Correct 3 ms 4076 KB Output is correct
5 Correct 1 ms 1900 KB Output is correct
6 Correct 7 ms 7296 KB Output is correct
7 Correct 1 ms 1260 KB Output is correct
8 Correct 3 ms 3308 KB Output is correct
9 Correct 16 ms 10988 KB Output is correct
10 Correct 26 ms 20204 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 5 ms 5228 KB Output is correct
14 Correct 1 ms 876 KB Output is correct
15 Correct 2 ms 2028 KB Output is correct
16 Correct 11 ms 10220 KB Output is correct
17 Correct 11 ms 9836 KB Output is correct
18 Correct 17 ms 14572 KB Output is correct
19 Correct 2 ms 2412 KB Output is correct
20 Correct 21 ms 20204 KB Output is correct
21 Correct 45 ms 49024 KB Output is correct
22 Correct 23 ms 25964 KB Output is correct
23 Correct 138 ms 144280 KB Output is correct
24 Runtime error 159 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -