Submission #1039570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039570		underwaterkillerwhale	Visiting Singapore (NOI20_visitingsingapore)	C++17	0 / 100	114 ms	262144 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 int INF = 2e9;
const int BASE = 137;

int n, K, m, A, B;
int dp[N][N], f[N][N], pt[N][N], ps[N][N];
int prt[N], pts[N];
int V[N];
int T[N], S[N];

inline void maximize (int &A, int 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];

    memset(dp, -0x3f, sizeof dp);
    memset(f, -0x3f, sizeof f);
    memset(ps, -0x3f, sizeof ps);
    memset(pt, -0x3f, sizeof pt);

    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]]);
                if (T[i - 1] == S[j - 1]) maximize(dp[i][j], dp[i - 1][j - 1] + V[T[i]]);
                maximize (dp[i][j], f[i - 1][j - 1] + 2 * A + B * i + B * j + V[T[i]]);
                maximize(dp[i][j], ps[i - 1][j - 1] + A + B * i + V[T[i]]);
                maximize(dp[i][j], pt[i - 1][j - 1] + A + B * j + V[T[i]]);

//                rep (k, 1, i - 1) {
//                    if (S[j - 1] == T[k]) {
//                        dp[i][j] = max(dp[i][j],
//                                   dp[k][j - 1] + A * (i - k >= 2) + B * (i - k - 1) + V[T[i]]);
//                    }
//                }
//                rep (k, 1, j - 1) {
//                    if (S[k] == T[i - 1]) {
//                        dp[i][j] = max(dp[i][j],
//                                   dp[i - 1][k] + A * (j - k >= 2) + B * (j - k - 1) + V[T[i]]);
//                    }
//                }
            }
            f[i][j] = max({f[i - 1][j], f[i][j - 1], dp[i][j] - B * (j + 1) - B * (i + 1)});
            pt[i][j] = max(pt[i][j - 1], dp[i][j] - B * (j + 1));
            ps[i][j] = max(ps[i - 1][j], dp[i][j] - B * (i + 1));
        }
    }
    int res = -INF;
    rep (i, 1, m)
    rep (j, 1, n) res = max(res, dp[i][j] + A * (i != m) + B * (m - i));
    cout << max(res, A + B * m)<<"\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