oj.uz

Submission #490880

# Submission time Handle Problem Language Result Execution time Memory
490880 2021-11-29T15:48:56 Z KienTran Visiting Singapore (NOI20_visitingsingapore) C++14
23 / 100
 150 ms 262148 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int O = 5e3 + 5;
const int inf = 1e18;

int k, n, m, a, b, v[O], s[O], t[O], f[2][O][O], dp[O][O];

main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    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 = 0; i <= n; ++ i){
        for (int j = 1; j <= m; ++ j){
            f[0][i][j] = -inf;
            f[1][i][j] = -inf;
            dp[i][j] = -inf;
        }
    }
    for (int j = 0; j <= m; ++ j) dp[0][j] = b * j;

    dp[0][0] = -inf;
    f[0][0][0] = f[1][0][0] = 0;
    for (int i = 1; i <= n; ++ i){
        for (int j = 1; j <= m; ++ j){
            f[0][i][j] = max(f[0][i - 1][j] + b, f[1][i - 1][j] + a + b);
            if (s[i] == t[j] && j) f[1][i][j] = max({dp[i - 1][j - 1] + a, f[0][i - 1][j - 1], f[1][i - 1][j - 1]}) + v[s[i]];
        }

        dp[i][0] = -inf;
        for (int j = 1; j <= m; ++ j)
            dp[i][j] = max({dp[i][j - 1], f[1][i][j - 1], f[0][i][j - 1]}) + b;
    }

    int res = a + b * m;
    for (int i = 0; i <= n; ++ i){
        for (int j = 0; j <= m; ++ j){
            int cost = max(f[0][i][j], f[1][i][j]) + a + b * (m - j);
            if (j == m) cost -= a;
            res = max(res, cost);
        }
    }

    cout << res;
}

Compilation message

VisitingSingapore.cpp:11:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   11 | main(){
      | ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3276 KB Output is correct
2 Correct 19 ms 31776 KB Output is correct
3 Correct 2 ms 3532 KB Output is correct
4 Correct 5 ms 11212 KB Output is correct
5 Correct 2 ms 4812 KB Output is correct
6 Correct 8 ms 15180 KB Output is correct
7 Correct 2 ms 2808 KB Output is correct
8 Correct 4 ms 7372 KB Output is correct
9 Correct 12 ms 20940 KB Output is correct
10 Correct 22 ms 35932 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 6 ms 9324 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 3 ms 3788 KB Output is correct
6 Correct 13 ms 18764 KB Output is correct
7 Correct 12 ms 17740 KB Output is correct
8 Correct 17 ms 26572 KB Output is correct
9 Correct 2 ms 4792 KB Output is correct
10 Correct 23 ms 35916 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 89292 KB Output is correct
2 Correct 29 ms 53812 KB Output is correct
3 Correct 150 ms 239044 KB Output is correct
4 Runtime error 112 ms 262148 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 89292 KB Output is correct
2 Correct 29 ms 53812 KB Output is correct
3 Correct 150 ms 239044 KB Output is correct
4 Runtime error 112 ms 262148 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 89292 KB Output is correct
2 Correct 29 ms 53812 KB Output is correct
3 Correct 150 ms 239044 KB Output is correct
4 Runtime error 112 ms 262148 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 1356 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 1228 KB Output is correct
10 Correct 1 ms 1740 KB Output is correct
11 Correct 1 ms 1740 KB Output is correct
12 Correct 1 ms 1740 KB Output is correct
13 Correct 1 ms 1740 KB Output is correct
14 Correct 1 ms 1740 KB Output is correct
15 Correct 1 ms 1740 KB Output is correct

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3276 KB Output is correct
2 Correct 19 ms 31776 KB Output is correct
3 Correct 2 ms 3532 KB Output is correct
4 Correct 5 ms 11212 KB Output is correct
5 Correct 2 ms 4812 KB Output is correct
6 Correct 8 ms 15180 KB Output is correct
7 Correct 2 ms 2808 KB Output is correct
8 Correct 4 ms 7372 KB Output is correct
9 Correct 12 ms 20940 KB Output is correct
10 Correct 22 ms 35932 KB Output is correct
11 Correct 1 ms 716 KB Output is correct
12 Correct 1 ms 588 KB Output is correct
13 Correct 6 ms 9324 KB Output is correct
14 Correct 1 ms 1484 KB Output is correct
15 Correct 3 ms 3788 KB Output is correct
16 Correct 13 ms 18764 KB Output is correct
17 Correct 12 ms 17740 KB Output is correct
18 Correct 17 ms 26572 KB Output is correct
19 Correct 2 ms 4792 KB Output is correct
20 Correct 23 ms 35916 KB Output is correct
21 Correct 49 ms 89292 KB Output is correct
22 Correct 29 ms 53812 KB Output is correct
23 Correct 150 ms 239044 KB Output is correct
24 Runtime error 112 ms 262148 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -