oj.uz

Submission #680893

# Submission time Handle Problem Language Result Execution time Memory
680893 2023-01-12T01:33:38 Z DennisTran Visiting Singapore (NOI20_visitingsingapore) C++17
0 / 100
 115 ms 262144 KB 
#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

using namespace std;

const int MAXN = 5005;
const int INF = 0x3f3f3f3f;

int K, N, M, A, B, v[MAXN], s[MAXN], t[MAXN];
int dp[MAXN][MAXN], Max[MAXN][MAXN], Event[MAXN][MAXN], Ord[MAXN][MAXN];

signed main(void) {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    //file("TASK");
    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, -INF, sizeof dp);
    memset(Max, -INF, sizeof Max);
    memset(Event, -INF, sizeof Event);
    memset(Ord, -INF, sizeof Ord);
    FOR(i, 1, N) FOR(j, 1, M) {
        if (s[i] == t[j]) {
            dp[i][j] = dp[i - 1][j - 1] + v[t[j]];
            if (i >= 2 && j >= 2)
                dp[i][j] = max(dp[i][j], Max[i - 2][j - 2] + v[t[j]] + B * (i + j) + 2 * (A - B));
            if (j >= 2)
                dp[i][j] = max(dp[i][j], Event[i - 1][j - 2] + v[t[j]] + B * j + A - B);
            if (i >= 2)
                dp[i][j] = max(dp[i][j], Ord[i - 2][j - 1] + v[t[j]] + B * i + A - B);
             dp[i][j] = max(dp[i][j], v[t[j]] + (j > 1) * A + (j - 1) * B);
        }

        Max[i][j] = dp[i][j] - B *(i + j);
        Max[i][j] = max(Max[i][j], Max[i - 1][j]);
        Max[i][j] = max(Max[i][j], Max[i][j - 1]);
        Event[i][j] = dp[i][j] - j * B;
        Event[i][j] = max(Event[i][j], Event[i][j - 1]);
        Ord[i][j] = dp[i][j] - i * B;
        Ord[i][j] = max(Ord[i][j], Ord[i - 1][j]);
    }
    int ans = -INF;
    FOR(i, 0, N) FOR(j, 0, M) if (dp[i][j] != -INF)
        ans = max(ans, dp[i][j] + (M > j) * A + (M - j) * B);
    cout << ans;
    cerr << "Time elapsed: " << TIME << " s.\n";
    return (0 ^ 0);
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 107 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 115 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 97 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 97 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 97 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 98 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 107 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -