oj.uz

Submission #691593

# Submission time Handle Problem Language Result Execution time Memory
691593 2023-01-31T10:06:06 Z penguin133 Visiting Singapore (NOI20_visitingsingapore) C++17
16 / 100
 918 ms 197332 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif

int S[5005], T[5005], V[5005], memo[5005][5005], n, m, k, a, b;

int dp(int x, int y){
	if(x == n + 1 || y == m + 1)return 0;
	if(memo[x][y] != -1)return memo[x][y];
	int res = max(dp(x+1, y), dp(x, y+1));
	if(S[x] == T[y])res = max(res, dp(x+1, y+1) + V[S[x]]);
	return memo[x][y] = 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];
	memset(memo, -1, sizeof(memo));
	cout << dp(1, 1) << '\n';
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

VisitingSingapore.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main(){
      | ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 196376 KB Output is correct
2 Correct 89 ms 196484 KB Output is correct
3 Correct 76 ms 196344 KB Output is correct
4 Correct 74 ms 196432 KB Output is correct
5 Correct 76 ms 196356 KB Output is correct
6 Correct 75 ms 196480 KB Output is correct
7 Correct 70 ms 196412 KB Output is correct
8 Correct 78 ms 196496 KB Output is correct
9 Correct 81 ms 196564 KB Output is correct
10 Correct 99 ms 196556 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 196396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 196720 KB Output is correct
2 Correct 102 ms 196604 KB Output is correct
3 Correct 347 ms 196940 KB Output is correct
4 Correct 661 ms 197084 KB Output is correct
5 Correct 217 ms 196840 KB Output is correct
6 Correct 298 ms 196932 KB Output is correct
7 Correct 557 ms 197124 KB Output is correct
8 Correct 223 ms 196940 KB Output is correct
9 Correct 349 ms 196976 KB Output is correct
10 Correct 823 ms 197292 KB Output is correct
11 Correct 837 ms 197292 KB Output is correct
12 Correct 846 ms 197288 KB Output is correct
13 Correct 918 ms 197276 KB Output is correct
14 Correct 774 ms 197332 KB Output is correct
15 Correct 712 ms 197264 KB Output is correct

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 196720 KB Output is correct
2 Correct 102 ms 196604 KB Output is correct
3 Correct 347 ms 196940 KB Output is correct
4 Correct 661 ms 197084 KB Output is correct
5 Correct 217 ms 196840 KB Output is correct
6 Correct 298 ms 196932 KB Output is correct
7 Correct 557 ms 197124 KB Output is correct
8 Correct 223 ms 196940 KB Output is correct
9 Correct 349 ms 196976 KB Output is correct
10 Correct 823 ms 197292 KB Output is correct
11 Correct 837 ms 197292 KB Output is correct
12 Correct 846 ms 197288 KB Output is correct
13 Correct 918 ms 197276 KB Output is correct
14 Correct 774 ms 197332 KB Output is correct
15 Correct 712 ms 197264 KB Output is correct
16 Incorrect 497 ms 197052 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 196720 KB Output is correct
2 Correct 102 ms 196604 KB Output is correct
3 Correct 347 ms 196940 KB Output is correct
4 Correct 661 ms 197084 KB Output is correct
5 Correct 217 ms 196840 KB Output is correct
6 Correct 298 ms 196932 KB Output is correct
7 Correct 557 ms 197124 KB Output is correct
8 Correct 223 ms 196940 KB Output is correct
9 Correct 349 ms 196976 KB Output is correct
10 Correct 823 ms 197292 KB Output is correct
11 Correct 837 ms 197292 KB Output is correct
12 Correct 846 ms 197288 KB Output is correct
13 Correct 918 ms 197276 KB Output is correct
14 Correct 774 ms 197332 KB Output is correct
15 Correct 712 ms 197264 KB Output is correct
16 Incorrect 706 ms 197204 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 196296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 196376 KB Output is correct
2 Correct 89 ms 196484 KB Output is correct
3 Correct 76 ms 196344 KB Output is correct
4 Correct 74 ms 196432 KB Output is correct
5 Correct 76 ms 196356 KB Output is correct
6 Correct 75 ms 196480 KB Output is correct
7 Correct 70 ms 196412 KB Output is correct
8 Correct 78 ms 196496 KB Output is correct
9 Correct 81 ms 196564 KB Output is correct
10 Correct 99 ms 196556 KB Output is correct
11 Incorrect 72 ms 196396 KB Output isn't correct
12 Halted 0 ms 0 KB -