답안 #680899

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
680899	2023-01-12T01:57:25 Z	DennisTran	Visiting Singapore (NOI20_visitingsingapore)	C++17	10 / 100	219 ms	196500 KB

VisitingSingapore

#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], Ord[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(Ord, -INF, sizeof Ord);
    FOR(i, 1, N) {
        int cur = -INF;
        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], cur + v[t[j]] + B * j + A - B);
                if (i >= 2)
                    dp[i][j] = max(dp[i][j], Ord[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]);
            if (j >= 1) cur = max(cur, dp[i - 1][j - 1] - (j - 1) * B);
            //Ord[i][j] = dp[i][j] - i * B;
            //Ord[i][j] = max(Ord[i][j], Ord[i - 1][j]);
        }
        if (i >= 1) {
            FOR(j, 1, M) {
                Ord[j] = max(Ord[j], dp[i - 1][j] - (i - 1) * B);
            }
        }
    }
    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
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	69 ms	196428 KB	Output is correct
2	Correct	93 ms	196428 KB	Output is correct
3	Correct	85 ms	196360 KB	Output is correct
4	Correct	72 ms	196388 KB	Output is correct
5	Correct	72 ms	196328 KB	Output is correct
6	Correct	73 ms	196412 KB	Output is correct
7	Correct	76 ms	196308 KB	Output is correct
8	Correct	73 ms	196372 KB	Output is correct
9	Correct	74 ms	196432 KB	Output is correct
10	Correct	76 ms	196384 KB	Output is correct

Subtask #2
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	70 ms	196316 KB	Output is correct
2	Correct	74 ms	196348 KB	Output is correct
3	Correct	76 ms	196340 KB	Output is correct
4	Correct	75 ms	196424 KB	Output is correct
5	Correct	73 ms	196396 KB	Output is correct
6	Correct	84 ms	196428 KB	Output is correct
7	Correct	76 ms	196376 KB	Output is correct
8	Correct	82 ms	196424 KB	Output is correct
9	Correct	72 ms	196384 KB	Output is correct
10	Correct	79 ms	196360 KB	Output is correct

Subtask #3
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	99 ms	196348 KB	Output is correct
2	Correct	84 ms	196352 KB	Output is correct
3	Correct	114 ms	196468 KB	Output is correct
4	Correct	167 ms	196452 KB	Output is correct
5	Correct	98 ms	196352 KB	Output is correct
6	Correct	115 ms	196444 KB	Output is correct
7	Correct	149 ms	196484 KB	Output is correct
8	Correct	117 ms	196476 KB	Output is correct
9	Correct	124 ms	196500 KB	Output is correct
10	Correct	198 ms	196496 KB	Output is correct
11	Correct	199 ms	196492 KB	Output is correct
12	Correct	219 ms	196496 KB	Output is correct
13	Incorrect	216 ms	196472 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #4
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	99 ms	196348 KB	Output is correct
2	Correct	84 ms	196352 KB	Output is correct
3	Correct	114 ms	196468 KB	Output is correct
4	Correct	167 ms	196452 KB	Output is correct
5	Correct	98 ms	196352 KB	Output is correct
6	Correct	115 ms	196444 KB	Output is correct
7	Correct	149 ms	196484 KB	Output is correct
8	Correct	117 ms	196476 KB	Output is correct
9	Correct	124 ms	196500 KB	Output is correct
10	Correct	198 ms	196496 KB	Output is correct
11	Correct	199 ms	196492 KB	Output is correct
12	Correct	219 ms	196496 KB	Output is correct
13	Incorrect	216 ms	196472 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #5
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	99 ms	196348 KB	Output is correct
2	Correct	84 ms	196352 KB	Output is correct
3	Correct	114 ms	196468 KB	Output is correct
4	Correct	167 ms	196452 KB	Output is correct
5	Correct	98 ms	196352 KB	Output is correct
6	Correct	115 ms	196444 KB	Output is correct
7	Correct	149 ms	196484 KB	Output is correct
8	Correct	117 ms	196476 KB	Output is correct
9	Correct	124 ms	196500 KB	Output is correct
10	Correct	198 ms	196496 KB	Output is correct
11	Correct	199 ms	196492 KB	Output is correct
12	Correct	219 ms	196496 KB	Output is correct
13	Incorrect	216 ms	196472 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	196300 KB	Output is correct
2	Correct	71 ms	196428 KB	Output is correct
3	Correct	75 ms	196412 KB	Output is correct
4	Correct	73 ms	196340 KB	Output is correct
5	Correct	74 ms	196384 KB	Output is correct
6	Correct	74 ms	196412 KB	Output is correct
7	Correct	72 ms	196344 KB	Output is correct
8	Correct	70 ms	196428 KB	Output is correct
9	Correct	74 ms	196340 KB	Output is correct
10	Correct	71 ms	196336 KB	Output is correct
11	Correct	87 ms	196428 KB	Output is correct
12	Correct	77 ms	196376 KB	Output is correct
13	Incorrect	73 ms	196408 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #7
0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	69 ms	196428 KB	Output is correct
2	Correct	93 ms	196428 KB	Output is correct
3	Correct	85 ms	196360 KB	Output is correct
4	Correct	72 ms	196388 KB	Output is correct
5	Correct	72 ms	196328 KB	Output is correct
6	Correct	73 ms	196412 KB	Output is correct
7	Correct	76 ms	196308 KB	Output is correct
8	Correct	73 ms	196372 KB	Output is correct
9	Correct	74 ms	196432 KB	Output is correct
10	Correct	76 ms	196384 KB	Output is correct
11	Correct	70 ms	196316 KB	Output is correct
12	Correct	74 ms	196348 KB	Output is correct
13	Correct	76 ms	196340 KB	Output is correct
14	Correct	75 ms	196424 KB	Output is correct
15	Correct	73 ms	196396 KB	Output is correct
16	Correct	84 ms	196428 KB	Output is correct
17	Correct	76 ms	196376 KB	Output is correct
18	Correct	82 ms	196424 KB	Output is correct
19	Correct	72 ms	196384 KB	Output is correct
20	Correct	79 ms	196360 KB	Output is correct
21	Correct	99 ms	196348 KB	Output is correct
22	Correct	84 ms	196352 KB	Output is correct
23	Correct	114 ms	196468 KB	Output is correct
24	Correct	167 ms	196452 KB	Output is correct
25	Correct	98 ms	196352 KB	Output is correct
26	Correct	115 ms	196444 KB	Output is correct
27	Correct	149 ms	196484 KB	Output is correct
28	Correct	117 ms	196476 KB	Output is correct
29	Correct	124 ms	196500 KB	Output is correct
30	Correct	198 ms	196496 KB	Output is correct
31	Correct	199 ms	196492 KB	Output is correct
32	Correct	219 ms	196496 KB	Output is correct
33	Incorrect	216 ms	196472 KB	Output isn't correct
34	Halted	0 ms	0 KB	-

답안 #680899

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 6.0 / 6.0

Subtask #3 0 / 12.0

Subtask #4 0 / 7.0

Subtask #5 0 / 8.0

Subtask #6 0 / 13.0

Subtask #7 0 / 50.0

Subtask #1
4.0 / 4.0

Subtask #2
6.0 / 6.0

Subtask #3
0 / 12.0

Subtask #4
0 / 7.0

Subtask #5
0 / 8.0

Subtask #6
0 / 13.0

Subtask #7
0 / 50.0