oj.uz

Submission #1039534

# Submission time Handle Problem Language Result Execution time Memory
1039534 2024-07-31T03:38:34 Z underwaterkillerwhale Visiting Singapore (NOI20_visitingsingapore) C++17
10 / 100
 1727 ms 213328 KB 
#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 5e3 + 7;
const int Mod = 1e9 + 7;
const int szBL = 240;
const ll INF = 1e18;
const int BASE = 137;

int n, K, m;
ll A, B;
ll dp[N][N];
int V[N];
int T[N], S[N];
int lst[N][N];

inline void maximize (ll &A, ll B) { if (A < B) A = B; }

void solution () {
    cin >> K >> n >> m >> A >> B;
    rep (i, 1, K) cin >> V[i];
    rep (i, 1, n) cin >> S[i];
    rep (i, 1, m) cin >> T[i];
    rep (i, 1, K)
    rep (j, 1, n) {
        lst[i][j] = (S[j] == i) ? j : lst[i][j - 1];
    }
    rep (i, 0, m)
    rep (j, 0, n) dp[i][j] = -INF;
    dp[0][0] = 0;
    rep (j, 1, n) {
        rep (i, 1, m) {
            if (S[j] == T[i]) {
                if (i == 1) maximize(dp[i][j], V[T[1]]);
                else maximize (dp[i][j], A + B * (i - 1) + V[T[i]]);
                maximize (dp[i][j], dp[i][lst[T[i]][j - 1]]);
                rep (k, 1, i - 1) {
                    int t = lst[T[k]][j - 1];
                    dp[i][j] = max(dp[i][j],
                                   dp[k][t] + A * (i - k >= 2) + B * (i - k - 1) + A * (j - t >= 2) + B * (j - t - 1) + V[T[i]]);
                }
            }
        }
    }
    ll res = -INF;
    rep (i, 1, m)
    rep (j, 1, n) res = max(res, dp[i][j] + A * (i != m) + B * (m - i));
    cout << res <<"\n";
}
#define file(name) freopen(name".inp", "r", stdin); \
freopen(name".out", "w", stdout);
/*
*/
int main () {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*
no bug challenge +2
*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 1099 ms 10744 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 123 ms 3512 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 19 ms 1672 KB Output is correct
9 Correct 444 ms 6660 KB Output is correct
10 Correct 1430 ms 12376 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3932 KB Output is correct
2 Correct 3 ms 2016 KB Output is correct
3 Correct 274 ms 5212 KB Output is correct
4 Correct 5 ms 1116 KB Output is correct
5 Correct 55 ms 2652 KB Output is correct
6 Correct 536 ms 7260 KB Output is correct
7 Correct 630 ms 7772 KB Output is correct
8 Correct 853 ms 9304 KB Output is correct
9 Correct 43 ms 2396 KB Output is correct
10 Correct 1457 ms 12376 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 27480 KB Output is correct
2 Correct 12 ms 18524 KB Output is correct
3 Correct 534 ms 75180 KB Output is correct
4 Correct 763 ms 185808 KB Output is correct
5 Correct 1727 ms 62424 KB Output is correct
6 Correct 537 ms 83548 KB Output is correct
7 Correct 487 ms 141744 KB Output is correct
8 Correct 66 ms 63668 KB Output is correct
9 Correct 257 ms 107328 KB Output is correct
10 Correct 1719 ms 201916 KB Output is correct
11 Correct 1312 ms 204112 KB Output is correct
12 Correct 989 ms 210516 KB Output is correct
13 Incorrect 120 ms 213328 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 27480 KB Output is correct
2 Correct 12 ms 18524 KB Output is correct
3 Correct 534 ms 75180 KB Output is correct
4 Correct 763 ms 185808 KB Output is correct
5 Correct 1727 ms 62424 KB Output is correct
6 Correct 537 ms 83548 KB Output is correct
7 Correct 487 ms 141744 KB Output is correct
8 Correct 66 ms 63668 KB Output is correct
9 Correct 257 ms 107328 KB Output is correct
10 Correct 1719 ms 201916 KB Output is correct
11 Correct 1312 ms 204112 KB Output is correct
12 Correct 989 ms 210516 KB Output is correct
13 Incorrect 120 ms 213328 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 27480 KB Output is correct
2 Correct 12 ms 18524 KB Output is correct
3 Correct 534 ms 75180 KB Output is correct
4 Correct 763 ms 185808 KB Output is correct
5 Correct 1727 ms 62424 KB Output is correct
6 Correct 537 ms 83548 KB Output is correct
7 Correct 487 ms 141744 KB Output is correct
8 Correct 66 ms 63668 KB Output is correct
9 Correct 257 ms 107328 KB Output is correct
10 Correct 1719 ms 201916 KB Output is correct
11 Correct 1312 ms 204112 KB Output is correct
12 Correct 989 ms 210516 KB Output is correct
13 Incorrect 120 ms 213328 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Correct 0 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Incorrect 0 ms 860 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 1099 ms 10744 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 123 ms 3512 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 19 ms 1672 KB Output is correct
9 Correct 444 ms 6660 KB Output is correct
10 Correct 1430 ms 12376 KB Output is correct
11 Correct 15 ms 3932 KB Output is correct
12 Correct 3 ms 2016 KB Output is correct
13 Correct 274 ms 5212 KB Output is correct
14 Correct 5 ms 1116 KB Output is correct
15 Correct 55 ms 2652 KB Output is correct
16 Correct 536 ms 7260 KB Output is correct
17 Correct 630 ms 7772 KB Output is correct
18 Correct 853 ms 9304 KB Output is correct
19 Correct 43 ms 2396 KB Output is correct
20 Correct 1457 ms 12376 KB Output is correct
21 Correct 35 ms 27480 KB Output is correct
22 Correct 12 ms 18524 KB Output is correct
23 Correct 534 ms 75180 KB Output is correct
24 Correct 763 ms 185808 KB Output is correct
25 Correct 1727 ms 62424 KB Output is correct
26 Correct 537 ms 83548 KB Output is correct
27 Correct 487 ms 141744 KB Output is correct
28 Correct 66 ms 63668 KB Output is correct
29 Correct 257 ms 107328 KB Output is correct
30 Correct 1719 ms 201916 KB Output is correct
31 Correct 1312 ms 204112 KB Output is correct
32 Correct 989 ms 210516 KB Output is correct
33 Incorrect 120 ms 213328 KB Output isn't correct
34 Halted 0 ms 0 KB -