oj.uz

Submission #1039585

# Submission time Handle Problem Language Result Execution time Memory
1039585 2024-07-31T04:57:34 Z underwaterkillerwhale Visiting Singapore (NOI20_visitingsingapore) C++17
6 / 100
 105 ms 196696 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 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, 1, 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][j - 1] + A + B * i + V[T[i]]);
                maximize(dp[i][j], pt[i - 1][j & 1 ^ 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 & 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

VisitingSingapore.cpp: In function 'void solution()':
VisitingSingapore.cpp:51:48: 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
0 / 4.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 196692 KB Output is correct
2 Correct 82 ms 196636 KB Output is correct
3 Correct 84 ms 196688 KB Output is correct
4 Correct 80 ms 196680 KB Output is correct
5 Correct 82 ms 196544 KB Output is correct
6 Correct 90 ms 196624 KB Output is correct
7 Correct 90 ms 196572 KB Output is correct
8 Correct 91 ms 196688 KB Output is correct
9 Correct 83 ms 196692 KB Output is correct
10 Correct 102 ms 196492 KB Output is correct

Subtask #3
0 / 12.0

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

Subtask #4
0 / 7.0

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

Subtask #5
0 / 8.0

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

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 196552 KB Output is correct
2 Incorrect 88 ms 196692 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 50.0

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