oj.uz

Submission #490894

# Submission time Handle Problem Language Result Execution time Memory
490894 2021-11-29T16:09:06 Z KienTran Visiting Singapore (NOI20_visitingsingapore) C++14
4 / 100
 217 ms 262148 KB 
#include <bits/stdc++.h>

using namespace std;

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

int k, n, m, a, b, v[1005], s[O], t[O], f[3][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;
        }
    }
    for (int j = 0; j <= m; ++ j) f[2][0][j] = a + b * j;

    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]) f[1][i][j] = max({f[2][i - 1][j - 1], f[0][i - 1][j - 1], f[1][i - 1][j - 1]}) + v[s[i]];
            f[2][i][j] = max({f[2][i][j - 1], f[1][i][j - 1] + a, 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:10:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   10 | main(){
      | ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3148 KB Output is correct
2 Correct 15 ms 21692 KB Output is correct
3 Correct 2 ms 3276 KB Output is correct
4 Correct 5 ms 10956 KB Output is correct
5 Correct 2 ms 4800 KB Output is correct
6 Correct 10 ms 12392 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 4 ms 6528 KB Output is correct
9 Correct 11 ms 15276 KB Output is correct
10 Correct 18 ms 24140 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 5 ms 6604 KB Output is correct
4 Incorrect 1 ms 1228 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 60700 KB Output is correct
2 Correct 26 ms 42220 KB Output is correct
3 Correct 111 ms 142532 KB Output is correct
4 Runtime error 217 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 47 ms 60700 KB Output is correct
2 Correct 26 ms 42220 KB Output is correct
3 Correct 111 ms 142532 KB Output is correct
4 Runtime error 217 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 47 ms 60700 KB Output is correct
2 Correct 26 ms 42220 KB Output is correct
3 Correct 111 ms 142532 KB Output is correct
4 Runtime error 217 ms 262148 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3148 KB Output is correct
2 Correct 15 ms 21692 KB Output is correct
3 Correct 2 ms 3276 KB Output is correct
4 Correct 5 ms 10956 KB Output is correct
5 Correct 2 ms 4800 KB Output is correct
6 Correct 10 ms 12392 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 4 ms 6528 KB Output is correct
9 Correct 11 ms 15276 KB Output is correct
10 Correct 18 ms 24140 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 5 ms 6604 KB Output is correct
14 Incorrect 1 ms 1228 KB Output isn't correct
15 Halted 0 ms 0 KB -