oj.uz

Submission #337374

# Submission time Handle Problem Language Result Execution time Memory
337374 2020-12-20T10:22:35 Z iulia13 Visiting Singapore (NOI20_visitingsingapore) C++14
23 / 100
 318 ms 262148 KB 
#include <iostream>

using namespace std;
int v[1005];
int s[5005];
int t[5005];
int dp[5005][5005][2][2];
void maxi (int &a, int b)
{
    a = max(a, b);
}
int main()
{
    int k, n, m, a, b, j, i, ans = 0;
    cin >> k >> n >> m >> a >> b;
    ans = a + m * b;
    for (i = 1; i <= k; i++)
        cin >> v[i];
    for (i = 1; i <= n; i++)
        cin >> s[i];
    for (i = 1; i <= m; i++)
        cin >> t[i];
    for (j = 1; j <= m; j++)
        for (int st1 = 0; st1 < 2; st1++)
            for (int st2 = 0; st2 < 2; st2++)
                dp[0][j][st1][st2] = -2e9;
    for (i = 1; i <= n; i++)
        for (int st1 = 0; st1 < 2; st1++)
            for (int st2 = 0; st2 < 2; st2++)
                dp[i][0][st1][st2] = -2e9;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            for (int st1 = 0; st1 < 2; st1++)
                for (int st2 = 0; st2 < 2; st2++)
                {
                    if (st1 && st2)
                    {
                        if (s[i] == t[j])
                        {
                            int var = - 2e9;
                            maxi(var, dp[i - 1][j - 1][0][0] + v[s[i]]);
                            maxi(var, dp[i - 1][j - 1][0][1] + v[s[i]]);
                            maxi(var, dp[i - 1][j - 1][1][0] + v[s[i]]);
                            maxi(var, dp[i - 1][j - 1][1][1] + v[s[i]]);
                            if (j == 1)
                                maxi(var, v[s[i]]);
                            else
                                maxi(var, a + b * (j - 1) + v[s[i]]);
                            dp[i][j][st1][st2] = var;
                        }
                        else
                            dp[i][j][st1][st2] = -2e9;
                    }
                    else
                    if (st2)
                        dp[i][j][st1][st2] = max(dp[i - 1][j][0][1] + b, dp[i - 1][j][1][1] + a + b);
                    else
                    if (st1)
                        dp[i][j][st1][st2] = max(dp[i][j - 1][1][0] + b, dp[i][j - 1][1][1] + a + b);
                    else
                        dp[i][j][st1][st2] = max(dp[i][j - 1][0][0] + b, dp[i][j - 1][0][1] + a + b);
                    if (j == m)
                    maxi(ans, dp[i][j][st1][st2]);
                }

    cout << ans;
    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 21 ms 17516 KB Output is correct
3 Correct 2 ms 1516 KB Output is correct
4 Correct 3 ms 4076 KB Output is correct
5 Correct 2 ms 1920 KB Output is correct
6 Correct 7 ms 7148 KB Output is correct
7 Correct 1 ms 1260 KB Output is correct
8 Correct 4 ms 3308 KB Output is correct
9 Correct 12 ms 10988 KB Output is correct
10 Correct 24 ms 20076 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 6 ms 5228 KB Output is correct
4 Correct 1 ms 876 KB Output is correct
5 Correct 3 ms 2156 KB Output is correct
6 Correct 12 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 3 ms 2412 KB Output is correct
10 Correct 23 ms 20076 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 49132 KB Output is correct
2 Correct 24 ms 25964 KB Output is correct
3 Correct 153 ms 144248 KB Output is correct
4 Runtime error 318 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 48 ms 49132 KB Output is correct
2 Correct 24 ms 25964 KB Output is correct
3 Correct 153 ms 144248 KB Output is correct
4 Runtime error 318 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 48 ms 49132 KB Output is correct
2 Correct 24 ms 25964 KB Output is correct
3 Correct 153 ms 144248 KB Output is correct
4 Runtime error 318 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 364 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 1 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 21 ms 17516 KB Output is correct
3 Correct 2 ms 1516 KB Output is correct
4 Correct 3 ms 4076 KB Output is correct
5 Correct 2 ms 1920 KB Output is correct
6 Correct 7 ms 7148 KB Output is correct
7 Correct 1 ms 1260 KB Output is correct
8 Correct 4 ms 3308 KB Output is correct
9 Correct 12 ms 10988 KB Output is correct
10 Correct 24 ms 20076 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 6 ms 5228 KB Output is correct
14 Correct 1 ms 876 KB Output is correct
15 Correct 3 ms 2156 KB Output is correct
16 Correct 12 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 3 ms 2412 KB Output is correct
20 Correct 23 ms 20076 KB Output is correct
21 Correct 48 ms 49132 KB Output is correct
22 Correct 24 ms 25964 KB Output is correct
23 Correct 153 ms 144248 KB Output is correct
24 Runtime error 318 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -