oj.uz

Submission #1039531

# Submission time Handle Problem Language Result Execution time Memory
1039531 2024-07-31T03:35:37 Z underwaterkillerwhale Visiting Singapore (NOI20_visitingsingapore) C++17
4 / 100
 1626 ms 214864 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, 1, m)
    rep (j, 1, 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]]);

                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]]);
                }
//                cout << i <<" "<<j<<" "<<dp[i][j] <<"\n";
            }
        }
    }
    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 4444 KB Output is correct
2 Correct 1049 ms 15516 KB Output is correct
3 Correct 3 ms 6488 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 121 ms 3420 KB Output is correct
7 Correct 2 ms 2648 KB Output is correct
8 Correct 19 ms 1628 KB Output is correct
9 Correct 449 ms 6652 KB Output is correct
10 Correct 1385 ms 12120 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 30060 KB Output is correct
2 Correct 11 ms 21336 KB Output is correct
3 Correct 471 ms 77376 KB Output is correct
4 Correct 811 ms 187160 KB Output is correct
5 Correct 1537 ms 66644 KB Output is correct
6 Correct 513 ms 86804 KB Output is correct
7 Correct 490 ms 143184 KB Output is correct
8 Correct 62 ms 65624 KB Output is correct
9 Correct 235 ms 109648 KB Output is correct
10 Correct 1626 ms 203456 KB Output is correct
11 Correct 1337 ms 205652 KB Output is correct
12 Correct 859 ms 212052 KB Output is correct
13 Incorrect 114 ms 214864 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 30060 KB Output is correct
2 Correct 11 ms 21336 KB Output is correct
3 Correct 471 ms 77376 KB Output is correct
4 Correct 811 ms 187160 KB Output is correct
5 Correct 1537 ms 66644 KB Output is correct
6 Correct 513 ms 86804 KB Output is correct
7 Correct 490 ms 143184 KB Output is correct
8 Correct 62 ms 65624 KB Output is correct
9 Correct 235 ms 109648 KB Output is correct
10 Correct 1626 ms 203456 KB Output is correct
11 Correct 1337 ms 205652 KB Output is correct
12 Correct 859 ms 212052 KB Output is correct
13 Incorrect 114 ms 214864 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 30060 KB Output is correct
2 Correct 11 ms 21336 KB Output is correct
3 Correct 471 ms 77376 KB Output is correct
4 Correct 811 ms 187160 KB Output is correct
5 Correct 1537 ms 66644 KB Output is correct
6 Correct 513 ms 86804 KB Output is correct
7 Correct 490 ms 143184 KB Output is correct
8 Correct 62 ms 65624 KB Output is correct
9 Correct 235 ms 109648 KB Output is correct
10 Correct 1626 ms 203456 KB Output is correct
11 Correct 1337 ms 205652 KB Output is correct
12 Correct 859 ms 212052 KB Output is correct
13 Incorrect 114 ms 214864 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4700 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 4444 KB Output is correct
2 Correct 1049 ms 15516 KB Output is correct
3 Correct 3 ms 6488 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 121 ms 3420 KB Output is correct
7 Correct 2 ms 2648 KB Output is correct
8 Correct 19 ms 1628 KB Output is correct
9 Correct 449 ms 6652 KB Output is correct
10 Correct 1385 ms 12120 KB Output is correct
11 Incorrect 15 ms 9560 KB Output isn't correct
12 Halted 0 ms 0 KB -