Submission #1039595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039595		underwaterkillerwhale	Visiting Singapore (NOI20_visitingsingapore)	C++17	100 / 100	444 ms	196948 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 = 1e9;
const int BASE = 137;

int n, K, m, A, B;
int dp[N][N], f[N][N], pt[N][2], ps[N][2];
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);
    rep (i, 0, m) pt[i][0] = ps[i][0] = -INF;
    rep (j, 1, n) {
        rep (i, 0, m) ps[i][j & 1] = -INF;
        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 ^ 1] + A + B * i + V[T[i]]);
                maximize (dp[i][j], pt[i - 1][j & 1 ^ 1] + A + B * j + V[T[i]]);
//                cout << i<<" "<<j<<" "<<ps[i][j & 1 ^ 1]<<" "<<dp[i][j]<<"\n";
//                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 & 1] = max(pt[i][j & 1 ^ 1], dp[i][j] - B * (j + 1));
            ps[i][j & 1] = max(ps[i - 1][j & 1], 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
*/

Compilation message (stderr)

VisitingSingapore.cpp: In function 'void solution()':
VisitingSingapore.cpp:50:49: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   50 |                 maximize (dp[i][j], ps[i - 1][j & 1 ^ 1] + A + B * i + V[T[i]]);
      |                                               ~~^~~
VisitingSingapore.cpp:51:49: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   51 |                 maximize (dp[i][j], pt[i - 1][j & 1 ^ 1] + A + B * j + V[T[i]]);
      |                                               ~~^~~
VisitingSingapore.cpp:67:40: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   67 |             pt[i][j & 1] = max(pt[i][j & 1 ^ 1], dp[i][j] - B * (j + 1));
      |                                      ~~^~~

• Subtask 1: 4 / 4
• Subtask 2: 6 / 6
• Subtask 3: 12 / 12
• Subtask 4: 7 / 7
• Subtask 5: 8 / 8
• Subtask 6: 13 / 13
• Subtask 7: 50 / 50