oj.uz

Submission #340370

# Submission time Handle Problem Language Result Execution time Memory
340370 2020-12-27T13:30:54 Z apostoldaniel854 Visiting Singapore (NOI20_visitingsingapore) C++14
12 / 100
 1010 ms 748 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

const int MAX_N = 5000, INF = 1e9;
int dp[2][1 + MAX_N][2][2];
int V[1 + MAX_N];
int S[1 + MAX_N];
int T[1 + MAX_N];
int K, A, B, n, m;

void upd (int &a, int b) {
    if (a < b)
        a = b;
}

void recurence (int i, int j, int bi, int bj) {
    if (i < n && j < m && S[i + 1] == T[j + 1])
        upd (dp[1 - (i & 1)][j + 1][0][0], dp[i & 1][j][bi][bj] + V[S[i + 1]]);
    if (i < n)
        upd (dp[1 - (i & 1)][j][1][bj], dp[i & 1][j][bi][bj] - A - ((bi == 0) ? B : 0));
    if (j < m)
        upd (dp[i & 1][j + 1][bi][1], dp[i & 1][j][bi][bj] - ((bj == 0) ? A : 0) - B);
}

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    cin >> K >> n >> m >> A >> B; A = -A, B = -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 j = 0; j <= m; j++)
        for (int bi = 0; bi < 2; bi++)
            for (int bj = 0; bj < 2; bj++)
                dp[0][j][bi][bj] = -INF;
    dp[0][0][0][0] = 0;
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++)
            for (int bi = 0; bi < 2; bi++)
                for (int bj = 0; bj < 2; bj++)
                    dp[1 - (i & 1)][j][bi][bj] = -INF;
        for (int j = 0; j <= m; j++)
            for (int bi = 0; bi < 2; bi++)
                for (int bj = 0; bj < 2; bj++)
                    recurence (i, j, bi, bj);
    }
    for (int bi = 0; bi < 2; bi++)
        for (int bj = 0; bj < 2; bj++)
            upd (ans, dp[n & 1][m][bi][bj]);
    cout << ans << "\n";
    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 364 KB Output is correct
2 Correct 37 ms 364 KB Output is correct
3 Correct 318 ms 620 KB Output is correct
4 Correct 754 ms 620 KB Output is correct
5 Correct 222 ms 620 KB Output is correct
6 Correct 317 ms 620 KB Output is correct
7 Correct 588 ms 620 KB Output is correct
8 Correct 191 ms 620 KB Output is correct
9 Correct 386 ms 492 KB Output is correct
10 Correct 925 ms 748 KB Output is correct
11 Correct 919 ms 748 KB Output is correct
12 Correct 938 ms 748 KB Output is correct
13 Correct 827 ms 748 KB Output is correct
14 Correct 986 ms 620 KB Output is correct
15 Correct 1010 ms 620 KB Output is correct

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 364 KB Output is correct
2 Correct 37 ms 364 KB Output is correct
3 Correct 318 ms 620 KB Output is correct
4 Correct 754 ms 620 KB Output is correct
5 Correct 222 ms 620 KB Output is correct
6 Correct 317 ms 620 KB Output is correct
7 Correct 588 ms 620 KB Output is correct
8 Correct 191 ms 620 KB Output is correct
9 Correct 386 ms 492 KB Output is correct
10 Correct 925 ms 748 KB Output is correct
11 Correct 919 ms 748 KB Output is correct
12 Correct 938 ms 748 KB Output is correct
13 Correct 827 ms 748 KB Output is correct
14 Correct 986 ms 620 KB Output is correct
15 Correct 1010 ms 620 KB Output is correct
16 Incorrect 482 ms 620 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 364 KB Output is correct
2 Correct 37 ms 364 KB Output is correct
3 Correct 318 ms 620 KB Output is correct
4 Correct 754 ms 620 KB Output is correct
5 Correct 222 ms 620 KB Output is correct
6 Correct 317 ms 620 KB Output is correct
7 Correct 588 ms 620 KB Output is correct
8 Correct 191 ms 620 KB Output is correct
9 Correct 386 ms 492 KB Output is correct
10 Correct 925 ms 748 KB Output is correct
11 Correct 919 ms 748 KB Output is correct
12 Correct 938 ms 748 KB Output is correct
13 Correct 827 ms 748 KB Output is correct
14 Correct 986 ms 620 KB Output is correct
15 Correct 1010 ms 620 KB Output is correct
16 Incorrect 767 ms 620 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -