oj.uz

Submission #692472

# Submission time Handle Problem Language Result Execution time Memory
692472 2023-02-01T13:50:32 Z saayan007 Visiting Singapore (NOI20_visitingsingapore) C++17
4 / 100
 194 ms 195884 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;
        }
    }

    dp[0][0] = 0;
    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);
            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 13 ms 6968 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 3 ms 2132 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 4 ms 3924 KB Output is correct
10 Correct 10 ms 8168 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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19156 KB Output is correct
2 Correct 9 ms 7816 KB Output is correct
3 Correct 64 ms 64468 KB Output is correct
4 Correct 143 ms 156388 KB Output is correct
5 Correct 44 ms 45620 KB Output is correct
6 Correct 65 ms 66576 KB Output is correct
7 Correct 117 ms 124316 KB Output is correct
8 Correct 39 ms 40712 KB Output is correct
9 Correct 73 ms 79744 KB Output is correct
10 Correct 194 ms 195404 KB Output is correct
11 Correct 175 ms 194824 KB Output is correct
12 Correct 181 ms 195884 KB Output is correct
13 Incorrect 179 ms 195796 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19156 KB Output is correct
2 Correct 9 ms 7816 KB Output is correct
3 Correct 64 ms 64468 KB Output is correct
4 Correct 143 ms 156388 KB Output is correct
5 Correct 44 ms 45620 KB Output is correct
6 Correct 65 ms 66576 KB Output is correct
7 Correct 117 ms 124316 KB Output is correct
8 Correct 39 ms 40712 KB Output is correct
9 Correct 73 ms 79744 KB Output is correct
10 Correct 194 ms 195404 KB Output is correct
11 Correct 175 ms 194824 KB Output is correct
12 Correct 181 ms 195884 KB Output is correct
13 Incorrect 179 ms 195796 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19156 KB Output is correct
2 Correct 9 ms 7816 KB Output is correct
3 Correct 64 ms 64468 KB Output is correct
4 Correct 143 ms 156388 KB Output is correct
5 Correct 44 ms 45620 KB Output is correct
6 Correct 65 ms 66576 KB Output is correct
7 Correct 117 ms 124316 KB Output is correct
8 Correct 39 ms 40712 KB Output is correct
9 Correct 73 ms 79744 KB Output is correct
10 Correct 194 ms 195404 KB Output is correct
11 Correct 175 ms 194824 KB Output is correct
12 Correct 181 ms 195884 KB Output is correct
13 Incorrect 179 ms 195796 KB Output isn't correct
14 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 1 ms 340 KB Output is correct
2 Correct 13 ms 6968 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 3 ms 2132 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 4 ms 3924 KB Output is correct
10 Correct 10 ms 8168 KB Output is correct
11 Incorrect 1 ms 340 KB Output isn't correct
12 Halted 0 ms 0 KB -