oj.uz

Submission #692471

# Submission time Handle Problem Language Result Execution time Memory
692471 2023-02-01T13:49:09 Z saayan007 Visiting Singapore (NOI20_visitingsingapore) C++17
16 / 100
 237 ms 195896 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] = {};
    ll res = -inf;
    fur(i, 1, n) {
        fur(j, 1, m) {
            dp[i][j] = max(dp[i - 1][j] + b, dp[i][j - 1] + b);
            // dp[i][j] = dp[i - 1][j] + (i > 1 ? b : 0), dp[i][j - 1] + (j > 1 ? b : 0));
            if(s[i] == t[j]) {
                dp[i][j] = max(dp[i][j], v[s[i]] + b * (j - 1));
                if(i > 1 && 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 1 ms 340 KB Output is correct
2 Correct 9 ms 6868 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 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 1 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 18 ms 19268 KB Output is correct
2 Correct 9 ms 7892 KB Output is correct
3 Correct 61 ms 64540 KB Output is correct
4 Correct 142 ms 156424 KB Output is correct
5 Correct 43 ms 45652 KB Output is correct
6 Correct 62 ms 66600 KB Output is correct
7 Correct 114 ms 124464 KB Output is correct
8 Correct 39 ms 40740 KB Output is correct
9 Correct 74 ms 79772 KB Output is correct
10 Correct 183 ms 195404 KB Output is correct
11 Correct 173 ms 194856 KB Output is correct
12 Correct 175 ms 195784 KB Output is correct
13 Correct 185 ms 195896 KB Output is correct
14 Correct 224 ms 195400 KB Output is correct
15 Correct 237 ms 195204 KB Output is correct

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19268 KB Output is correct
2 Correct 9 ms 7892 KB Output is correct
3 Correct 61 ms 64540 KB Output is correct
4 Correct 142 ms 156424 KB Output is correct
5 Correct 43 ms 45652 KB Output is correct
6 Correct 62 ms 66600 KB Output is correct
7 Correct 114 ms 124464 KB Output is correct
8 Correct 39 ms 40740 KB Output is correct
9 Correct 74 ms 79772 KB Output is correct
10 Correct 183 ms 195404 KB Output is correct
11 Correct 173 ms 194856 KB Output is correct
12 Correct 175 ms 195784 KB Output is correct
13 Correct 185 ms 195896 KB Output is correct
14 Correct 224 ms 195400 KB Output is correct
15 Correct 237 ms 195204 KB Output is correct
16 Incorrect 93 ms 101964 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19268 KB Output is correct
2 Correct 9 ms 7892 KB Output is correct
3 Correct 61 ms 64540 KB Output is correct
4 Correct 142 ms 156424 KB Output is correct
5 Correct 43 ms 45652 KB Output is correct
6 Correct 62 ms 66600 KB Output is correct
7 Correct 114 ms 124464 KB Output is correct
8 Correct 39 ms 40740 KB Output is correct
9 Correct 74 ms 79772 KB Output is correct
10 Correct 183 ms 195404 KB Output is correct
11 Correct 173 ms 194856 KB Output is correct
12 Correct 175 ms 195784 KB Output is correct
13 Correct 185 ms 195896 KB Output is correct
14 Correct 224 ms 195400 KB Output is correct
15 Correct 237 ms 195204 KB Output is correct
16 Incorrect 151 ms 162908 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 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 1 ms 340 KB Output is correct
2 Correct 9 ms 6868 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 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 1 ms 340 KB Output isn't correct
12 Halted 0 ms 0 KB -