oj.uz

Submission #692474

# Submission time Handle Problem Language Result Execution time Memory
692474 2023-02-01T13:52:37 Z saayan007 Visiting Singapore (NOI20_visitingsingapore) C++17
23 / 100
 255 ms 196060 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpl = vector<pl>;

#define fur(i, a, b) for(ll i = a; i <= (ll) b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= (ll) b; --i)
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define nl "\n"

const ll inf = 1e10L;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll k, n, m, a, b;
    cin >> k >> n >> m >> a >> b;
    ll v[k + 1], s[n + 1], t[m + 1];

    fur(i, 1, k) {
        cin >> v[i];
    }
    fur(i, 1, n) {
        cin >> s[i];
    }
    fur(i, 1, m) {
        cin >> t[i];
    }

    ll dp[n + 1][m + 1];
    fur(i, 0, n) {
        fur(j, 0, m) {
            dp[i][j] = -inf;
        }
    }

    ll res = -inf;
    dp[0][0] = 0;
    fur(j, 1, m) {
        dp[0][j] = dp[0][j - 1] + b;   
    }
    res = max(res, dp[0][m]);

    fur(i, 1, n) {
        fur(j, 1, m) {

            dp[i][j] = max(dp[i - 1][j] + b, dp[i][j - 1] + b);

            if(s[i] == t[j]) {

                dp[i][j] = max(dp[i][j], v[s[i]] + b * (j - 1));
                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + v[s[i]]);

            }
        }
        res = max(res, dp[i][m]);
    }
    cout << res << nl;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 8 ms 6972 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 2 ms 2132 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 5 ms 3924 KB Output is correct
10 Correct 9 ms 8148 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 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 19 ms 19156 KB Output is correct
2 Correct 7 ms 7892 KB Output is correct
3 Correct 63 ms 64552 KB Output is correct
4 Correct 146 ms 156368 KB Output is correct
5 Correct 45 ms 45524 KB Output is correct
6 Correct 63 ms 66580 KB Output is correct
7 Correct 116 ms 124452 KB Output is correct
8 Correct 39 ms 40720 KB Output is correct
9 Correct 75 ms 79748 KB Output is correct
10 Correct 180 ms 195272 KB Output is correct
11 Correct 186 ms 194872 KB Output is correct
12 Correct 188 ms 195800 KB Output is correct
13 Correct 182 ms 195788 KB Output is correct
14 Correct 233 ms 195308 KB Output is correct
15 Correct 226 ms 195248 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19156 KB Output is correct
2 Correct 7 ms 7892 KB Output is correct
3 Correct 63 ms 64552 KB Output is correct
4 Correct 146 ms 156368 KB Output is correct
5 Correct 45 ms 45524 KB Output is correct
6 Correct 63 ms 66580 KB Output is correct
7 Correct 116 ms 124452 KB Output is correct
8 Correct 39 ms 40720 KB Output is correct
9 Correct 75 ms 79748 KB Output is correct
10 Correct 180 ms 195272 KB Output is correct
11 Correct 186 ms 194872 KB Output is correct
12 Correct 188 ms 195800 KB Output is correct
13 Correct 182 ms 195788 KB Output is correct
14 Correct 233 ms 195308 KB Output is correct
15 Correct 226 ms 195248 KB Output is correct
16 Correct 93 ms 101964 KB Output is correct
17 Correct 116 ms 123196 KB Output is correct
18 Correct 103 ms 109380 KB Output is correct
19 Correct 22 ms 22228 KB Output is correct
20 Correct 79 ms 77844 KB Output is correct
21 Correct 6 ms 4564 KB Output is correct
22 Correct 26 ms 25140 KB Output is correct
23 Correct 48 ms 49320 KB Output is correct
24 Correct 17 ms 17652 KB Output is correct
25 Correct 179 ms 195368 KB Output is correct
26 Correct 186 ms 195136 KB Output is correct
27 Correct 188 ms 196060 KB Output is correct
28 Correct 179 ms 195240 KB Output is correct
29 Correct 233 ms 194728 KB Output is correct
30 Correct 255 ms 194808 KB Output is correct

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19156 KB Output is correct
2 Correct 7 ms 7892 KB Output is correct
3 Correct 63 ms 64552 KB Output is correct
4 Correct 146 ms 156368 KB Output is correct
5 Correct 45 ms 45524 KB Output is correct
6 Correct 63 ms 66580 KB Output is correct
7 Correct 116 ms 124452 KB Output is correct
8 Correct 39 ms 40720 KB Output is correct
9 Correct 75 ms 79748 KB Output is correct
10 Correct 180 ms 195272 KB Output is correct
11 Correct 186 ms 194872 KB Output is correct
12 Correct 188 ms 195800 KB Output is correct
13 Correct 182 ms 195788 KB Output is correct
14 Correct 233 ms 195308 KB Output is correct
15 Correct 226 ms 195248 KB Output is correct
16 Incorrect 151 ms 162900 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 8 ms 6972 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 2 ms 2132 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 5 ms 3924 KB Output is correct
10 Correct 9 ms 8148 KB Output is correct
11 Incorrect 0 ms 340 KB Output isn't correct
12 Halted 0 ms 0 KB -