oj.uz

Submission #843778

# Submission time Handle Problem Language Result Execution time Memory
843778 2023-09-04T14:49:15 Z fanwen Visiting Singapore (NOI20_visitingsingapore) C++17
0 / 100
 33 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define debug(...) "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }
template <class T> T max(const T &a, const T &b, const T &c) { return max(max(a, b), c); }
template <class T> T min(const T &a, const T &b, const T &c) { return min(min(a, b), c); }

const int MAXN = 5e3 + 5;

int N, M, K, A, B;
int v[MAXN / 5], s[MAXN], t[MAXN];
int dp[MAXN][MAXN], Max[MAXN][MAXN], Max_i[MAXN][MAXN], Max_j[MAXN][MAXN];

void you_make_it(void) {
    cin >> K >> N >> M >> A >> B;
    FOR(i, 1, K) cin >> v[i];
    FOR(i, 1, N) cin >> s[i];
    FOR(i, 1, M) cin >> t[i];
    memset(dp, -0x3f, sizeof dp);
    memset(Max, -0x3f, sizeof Max);
    memset(Max_i, -0x3f, sizeof Max_i);
    memset(Max_j, -0x3f, sizeof Max_j);
    long long ans = M * B + A;
    FOR(i, 1, N) FOR(j, 1, M) {
        if(s[i] == t[j]) dp[i][j] = v[s[i]] + A * (j != 1) + (j - 1) * B;
    }
    FOR(i, 1, N) FOR(j, 1, M) {
        maximize(dp[i][j], max(Max[i - 1][j - 1] + (i + j) * B + 2 * A, Max_i[i][j - 1] + (i + j) * B + A, Max_j[i - 1][j] + (i + j) * B + A));
        if(s[i] == t[j]) maximize(dp[i][j], dp[i - 1][j - 1] + v[s[i]]), maximize(ans, dp[i][j] + A * (j != M) + (M - j) * B);
        Max[i][j] = max(Max[i - 1][j], Max[i][j - 1], dp[i][j] - (i + j) * B);
        Max_i[i][j] = max(dp[i][j] - (i + j) * B, Max_i[i][j - 1]);
        Max_j[i][j] = max(dp[i][j] - (i + j) * B, Max_j[i - 1][j]);
    }
    cout << ans;
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -