답안 #679729

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
679729 2023-01-09T03:23:36 Z DP_196 Visiting Singapore (NOI20_visitingsingapore) C++14
42 / 100
126 ms 262144 KB
#include <bits/stdc++.h>

using namespace std;

#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], dp[5005][5005][2][2];

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

void sub2() {
	int res = m * b;

	for (int j = 0; j <= m; j++) g[0][j] = j * b;
	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]]);
			maximize(res, g[i][j] + (m - j) * b);
		}
	
	cout << res;
}

void sub6() {	
	int res = a + m * b;
	for (int j = 0; j <= m; j++) f[0][j] = j * b;
	
	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 sub4() {
	int res = a;
	
	memset(dp, -0x3f, sizeof (dp));
	dp[0][0][0][0] = 0;
 	for (int i = 0; i <= m; i++) {
		dp[0][i][0][1] = a;
		dp[0][i][0][0] = a;
	}
	
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= m; j++) { 
			dp[i][j][0][0] = max({dp[i - 1][j][0][0], dp[i][j - 1][0][0], dp[i - 1][j - 1][1][1]});
			dp[i][j][0][1] = max(dp[i - 1][j][0][1], dp[i - 1][j][1][1]);
			dp[i][j][1][0] = max(dp[i][j - 1][1][0], dp[i][j - 1][1][1]);
			
			if (s[i] == t[j]) {
				dp[i][j][1][1] = v[s[i]] + (j > 1 ? a : 0);
				maximize(dp[i][j][1][1], dp[i - 1][j - 1][0][0] + 2 * a + v[s[i]]);
				maximize(dp[i][j][1][1], dp[i - 1][j - 1][0][1] + a + v[s[i]]);
				maximize(dp[i][j][1][1], dp[i - 1][j - 1][1][0] + a + v[s[i]]);
				maximize(dp[i][j][1][1], dp[i - 1][j - 1][1][1] + v[s[i]]);
			}
			
			maximize(res, dp[i][j][1][1] + (m - j >= 1 ? a : 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 (b == 0) sub4();
	else if (n <= 100 && m <= 100) sub6();
}

#define TASK "FUNTOUR"
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
   	//freopen(TASK".inp", "r", stdin);
   	//freopen(TASK".out", "w", stdout);

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

    return 0;
}
//612
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 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 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 20392 KB Output is correct
2 Correct 11 ms 14292 KB Output is correct
3 Correct 51 ms 47736 KB Output is correct
4 Correct 111 ms 88232 KB Output is correct
5 Correct 33 ms 28736 KB Output is correct
6 Correct 49 ms 43108 KB Output is correct
7 Correct 90 ms 81264 KB Output is correct
8 Correct 35 ms 34492 KB Output is correct
9 Correct 57 ms 51712 KB Output is correct
10 Correct 123 ms 98132 KB Output is correct
11 Correct 123 ms 97872 KB Output is correct
12 Correct 125 ms 98088 KB Output is correct
13 Correct 126 ms 98096 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 20392 KB Output is correct
2 Correct 11 ms 14292 KB Output is correct
3 Correct 51 ms 47736 KB Output is correct
4 Correct 111 ms 88232 KB Output is correct
5 Correct 33 ms 28736 KB Output is correct
6 Correct 49 ms 43108 KB Output is correct
7 Correct 90 ms 81264 KB Output is correct
8 Correct 35 ms 34492 KB Output is correct
9 Correct 57 ms 51712 KB Output is correct
10 Correct 123 ms 98132 KB Output is correct
11 Correct 123 ms 97872 KB Output is correct
12 Correct 125 ms 98088 KB Output is correct
13 Correct 126 ms 98096 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 77 ms 66780 KB Output is correct
17 Correct 89 ms 80860 KB Output is correct
18 Correct 81 ms 74568 KB Output is correct
19 Correct 17 ms 15876 KB Output is correct
20 Correct 60 ms 54112 KB Output is correct
21 Correct 6 ms 7764 KB Output is correct
22 Correct 19 ms 16440 KB Output is correct
23 Correct 37 ms 32420 KB Output is correct
24 Correct 18 ms 20212 KB Output is correct
25 Correct 124 ms 97896 KB Output is correct
26 Correct 124 ms 97952 KB Output is correct
27 Correct 126 ms 98200 KB Output is correct
28 Correct 125 ms 98096 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 20392 KB Output is correct
2 Correct 11 ms 14292 KB Output is correct
3 Correct 51 ms 47736 KB Output is correct
4 Correct 111 ms 88232 KB Output is correct
5 Correct 33 ms 28736 KB Output is correct
6 Correct 49 ms 43108 KB Output is correct
7 Correct 90 ms 81264 KB Output is correct
8 Correct 35 ms 34492 KB Output is correct
9 Correct 57 ms 51712 KB Output is correct
10 Correct 123 ms 98132 KB Output is correct
11 Correct 123 ms 97872 KB Output is correct
12 Correct 125 ms 98088 KB Output is correct
13 Correct 126 ms 98096 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Runtime error 99 ms 262144 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 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 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 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 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 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 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 18 ms 20392 KB Output is correct
22 Correct 11 ms 14292 KB Output is correct
23 Correct 51 ms 47736 KB Output is correct
24 Correct 111 ms 88232 KB Output is correct
25 Correct 33 ms 28736 KB Output is correct
26 Correct 49 ms 43108 KB Output is correct
27 Correct 90 ms 81264 KB Output is correct
28 Correct 35 ms 34492 KB Output is correct
29 Correct 57 ms 51712 KB Output is correct
30 Correct 123 ms 98132 KB Output is correct
31 Correct 123 ms 97872 KB Output is correct
32 Correct 125 ms 98088 KB Output is correct
33 Correct 126 ms 98096 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 77 ms 66780 KB Output is correct
37 Correct 89 ms 80860 KB Output is correct
38 Correct 81 ms 74568 KB Output is correct
39 Correct 17 ms 15876 KB Output is correct
40 Correct 60 ms 54112 KB Output is correct
41 Correct 6 ms 7764 KB Output is correct
42 Correct 19 ms 16440 KB Output is correct
43 Correct 37 ms 32420 KB Output is correct
44 Correct 18 ms 20212 KB Output is correct
45 Correct 124 ms 97896 KB Output is correct
46 Correct 124 ms 97952 KB Output is correct
47 Correct 126 ms 98200 KB Output is correct
48 Correct 125 ms 98096 KB Output is correct
49 Correct 1 ms 340 KB Output is correct
50 Correct 1 ms 340 KB Output is correct
51 Runtime error 99 ms 262144 KB Execution killed with signal 9
52 Halted 0 ms 0 KB -