oj.uz

Submission #337375

# Submission time Handle Problem Language Result Execution time Memory
337375 2020-12-20T10:28:36 Z iulia13 Visiting Singapore (NOI20_visitingsingapore) C++14
23 / 100
 276 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] = -1e9;
    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] = -1e9;
    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 = - 1e9;
                            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] = -1e9;
                    }
                    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 1 ms 1388 KB Output is correct
2 Correct 20 ms 17516 KB Output is correct
3 Correct 1 ms 1536 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 7148 KB Output is correct
7 Correct 1 ms 1388 KB Output is correct
8 Correct 3 ms 3308 KB Output is correct
9 Correct 12 ms 10988 KB Output is correct
10 Correct 23 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 6 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 16 ms 14444 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 49220 KB Output is correct
2 Correct 26 ms 25984 KB Output is correct
3 Correct 160 ms 144236 KB Output is correct
4 Runtime error 276 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 49220 KB Output is correct
2 Correct 26 ms 25984 KB Output is correct
3 Correct 160 ms 144236 KB Output is correct
4 Runtime error 276 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 49220 KB Output is correct
2 Correct 26 ms 25984 KB Output is correct
3 Correct 160 ms 144236 KB Output is correct
4 Runtime error 276 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 492 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 1 ms 1388 KB Output is correct
2 Correct 20 ms 17516 KB Output is correct
3 Correct 1 ms 1536 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 7148 KB Output is correct
7 Correct 1 ms 1388 KB Output is correct
8 Correct 3 ms 3308 KB Output is correct
9 Correct 12 ms 10988 KB Output is correct
10 Correct 23 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 6 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 16 ms 14444 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 49220 KB Output is correct
22 Correct 26 ms 25984 KB Output is correct
23 Correct 160 ms 144236 KB Output is correct
24 Runtime error 276 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -