답안 #678797

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
678797	2023-01-06T15:15:30 Z	DP_196	Visiting Singapore (NOI20_visitingsingapore)	C++14	22 / 100	160 ms	196044 KB

VisitingSingapore

#include <bits/stdc++.h>

using namespace std;

#define int int64_t
#define sz(x) (int)x.size()
#define MASK(i) ((1LL) << (i))
#define all(x) x.begin(), x.end()
#define BIT(x, i) ((x) >> (i) & (1LL))
#define dbg(...) cerr << "#" << __LINE__ << ":[" << #__VA_ARGS__ \
<< "] = [" ,DBG(__VA_ARGS__)

string to_string(const string& s) { return '"' + s + '"'; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
        cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...);
}

template <class T>
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b) : 0); }
template <class T>
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b) : 0); }

const int MAXN = 1e5 + 6;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int k, n, m, a, b, v[5005], s[5005], t[5005];
int g[5005][5005], f[105][105];

void sub1() {
	if (m <= n) return (void) (cout << (v[1] * m));
	cout << v[1] * n + (a + (m - n) * b);
}

void sub2() {
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			g[i][j] = max(g[i - 1][j], g[i][j - 1]) + b;
			if (s[i] == t[j]) maximize(g[i][j], g[i - 1][j - 1] + v[s[i]]);
		}
	
	cout << g[n][m];
}

void sub6() {	
	memset(f, -0x3f, sizeof (f));
	
	int res = f[0][0];
	f[0][0] = 0;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (s[i] != t[j]) continue;
			f[i][j] = v[s[i]] + (j > 1 ? a + (j - 1) * b : 0);
			for (int x = 1; x < i; x++)
				for (int y = 1; y < j; y++)
					if (s[x] == t[y]) maximize(f[i][j], v[s[i]] + f[x][y] + 
						(j - y >= 2 ? a + (j - y - 1) * b : 0) + (i - x >= 2 ? a + (i - x - 1) * b : 0));
			maximize(res, f[i][j] + (m != j ? a + (m - j) * b : 0));
		}
	}
	
	cout << res;
}                          

void solve() {
	cin >> k >> n >> m >> a >> b;
	
	for (int i = 1; i <= k; i++) cin >> v[i];
	for (int i = 1; i <= n; i++) cin >> s[i];
	for (int i = 1; i <= m; i++) cin >> t[i];
	
	if (k == 1) sub1();
	else if (a == 0) sub2();
	else if (n <= 100 && m <= 100) sub6();
}

#define TASK "FUNTOUR"
int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int ntest = 1;
    //cin >> ntest;
    while (ntest--) solve();

    return 0;
}
//612

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	1 ms	324 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct

Subtask #2
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	324 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	29968 KB	Output is correct
2	Correct	13 ms	18132 KB	Output is correct
3	Correct	64 ms	79828 KB	Output is correct
4	Correct	140 ms	174240 KB	Output is correct
5	Correct	46 ms	51444 KB	Output is correct
6	Correct	62 ms	76236 KB	Output is correct
7	Correct	111 ms	143384 KB	Output is correct
8	Correct	43 ms	54756 KB	Output is correct
9	Correct	71 ms	91404 KB	Output is correct
10	Correct	159 ms	196044 KB	Output is correct
11	Correct	157 ms	195472 KB	Output is correct
12	Correct	156 ms	196008 KB	Output is correct
13	Correct	160 ms	195916 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct

Subtask #4
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	29968 KB	Output is correct
2	Correct	13 ms	18132 KB	Output is correct
3	Correct	64 ms	79828 KB	Output is correct
4	Correct	140 ms	174240 KB	Output is correct
5	Correct	46 ms	51444 KB	Output is correct
6	Correct	62 ms	76236 KB	Output is correct
7	Correct	111 ms	143384 KB	Output is correct
8	Correct	43 ms	54756 KB	Output is correct
9	Correct	71 ms	91404 KB	Output is correct
10	Correct	159 ms	196044 KB	Output is correct
11	Correct	157 ms	195472 KB	Output is correct
12	Correct	156 ms	196008 KB	Output is correct
13	Correct	160 ms	195916 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Incorrect	94 ms	117720 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #5
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	29968 KB	Output is correct
2	Correct	13 ms	18132 KB	Output is correct
3	Correct	64 ms	79828 KB	Output is correct
4	Correct	140 ms	174240 KB	Output is correct
5	Correct	46 ms	51444 KB	Output is correct
6	Correct	62 ms	76236 KB	Output is correct
7	Correct	111 ms	143384 KB	Output is correct
8	Correct	43 ms	54756 KB	Output is correct
9	Correct	71 ms	91404 KB	Output is correct
10	Correct	159 ms	196044 KB	Output is correct
11	Correct	157 ms	195472 KB	Output is correct
12	Correct	156 ms	196008 KB	Output is correct
13	Correct	160 ms	195916 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Incorrect	1 ms	340 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	324 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	1 ms	324 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	328 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Incorrect	1 ms	332 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #7
0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	1 ms	324 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	1 ms	324 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	22 ms	29968 KB	Output is correct
22	Correct	13 ms	18132 KB	Output is correct
23	Correct	64 ms	79828 KB	Output is correct
24	Correct	140 ms	174240 KB	Output is correct
25	Correct	46 ms	51444 KB	Output is correct
26	Correct	62 ms	76236 KB	Output is correct
27	Correct	111 ms	143384 KB	Output is correct
28	Correct	43 ms	54756 KB	Output is correct
29	Correct	71 ms	91404 KB	Output is correct
30	Correct	159 ms	196044 KB	Output is correct
31	Correct	157 ms	195472 KB	Output is correct
32	Correct	156 ms	196008 KB	Output is correct
33	Correct	160 ms	195916 KB	Output is correct
34	Correct	1 ms	340 KB	Output is correct
35	Correct	1 ms	340 KB	Output is correct
36	Incorrect	94 ms	117720 KB	Output isn't correct
37	Halted	0 ms	0 KB	-

답안 #678797

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 6.0 / 6.0

Subtask #3 12.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
12.0 / 12.0

Subtask #4
0 / 7.0

Subtask #5
0 / 8.0

Subtask #6
0 / 13.0

Subtask #7
0 / 50.0