Submission #1039529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039529		underwaterkillerwhale	Visiting Singapore (NOI20_visitingsingapore)	C++17	0 / 100	115 ms	202320 KiB

VisitingSingapore

#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];
    }
    memset(dp, -0x3f, sizeof dp);
    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: 0 / 4
• Subtask 2: 0 / 6
• Subtask 3: 0 / 12
• Subtask 4: 0 / 7
• Subtask 5: 0 / 8
• Subtask 6: 0 / 13
• Subtask 7: 0 / 50