oj.uz

Submission #1091950

# Submission time Handle Problem Language Result Execution time Memory
1091950 2024-09-22T17:09:34 Z _rain_ Visiting Singapore (NOI20_visitingsingapore) C++14
12 / 100
 224 ms 716 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define fixbug true
 
const ll INF = (ll)1e18+7;
const int maxn = 5e3;
int K , n , m ;
ll A , B;
int s[maxn+2] , t[maxn+2] ;
ll v[maxn+2];
 
namespace subtaskfull{
	bool check(){
		return true;
	}
	ll sub(int x1 , int x , int y1 , int y){
		// x for T , y for S
		return A*(x1+y1) + B*(y+x);
	}
	// dp[S][T][MATCH/NOT] 
	ll dp[maxn+2][2] , f[maxn+2][2] , tam[maxn+2] , cot[maxn+2]={};
	void main_code(){
		memset(dp,-0x3f,sizeof dp);
		memset(tam,-0x3f,sizeof tam);
		for (int i = 0; i <= n; ++i) dp[i][1] = 0;
		ll ans = -INF;
		for (int layer = 1; layer <= m; ++layer) // T for 
		{
			for (int i = 0; i <= n; ++i){
				f[i][0] = dp[i][0] , f[i][1] = dp[i][1];
				dp[i][0] = dp[i][1] = tam[i] = -INF;
			}
			for (int i = 1; i <= n; ++i) // S for 
			{
				if (s[i] == t[layer])
				{
					dp[i][1] = max({
						f[i-1][0] , cot[i] , tam[i-1]
					}) + v[t[layer]];
				}
				dp[i][0] = max({
					f[i-1][1] + sub(1,1,1,1),
					f[i-1][0] + sub(0,1,0,1),
					f[i][0] + sub(0,0,0,1),
					f[i][1] + sub(0,0,1,1),
					dp[i-1][0] + sub(0,1,0,0),
					dp[i-1][1] + sub(1,1,0,0)
				});
				tam[i] = max({
					f[i-1][1] + sub(1,1,1,1),
					f[i-1][0] + sub(0,1,0,1),
					f[i][0] + sub(0,0,0,1),
					f[i][1] + sub(0,0,1,1),
					tam[i-1] + sub(0,1,0,0)
				});
				if (layer==1) cot[i] = cot[i] + sub(0,0,1,1); else cot[i] += sub(0,0,0,1);
			}
		}
		for (int i = 1; i <= n; ++i) ans = max({ans , dp[i][0],dp[i][1]});
		cout << ans;
	}
}
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	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 (subtaskfull::check()){
		subtaskfull::main_code();
		exit(0);
	}
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 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 25 ms 672 KB Output is correct
2 Correct 9 ms 604 KB Output is correct
3 Correct 69 ms 604 KB Output is correct
4 Correct 192 ms 716 KB Output is correct
5 Correct 53 ms 600 KB Output is correct
6 Correct 72 ms 604 KB Output is correct
7 Correct 138 ms 600 KB Output is correct
8 Correct 43 ms 604 KB Output is correct
9 Correct 84 ms 676 KB Output is correct
10 Correct 211 ms 604 KB Output is correct
11 Correct 207 ms 600 KB Output is correct
12 Correct 207 ms 600 KB Output is correct
13 Correct 204 ms 600 KB Output is correct
14 Correct 224 ms 604 KB Output is correct
15 Correct 223 ms 604 KB Output is correct

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 672 KB Output is correct
2 Correct 9 ms 604 KB Output is correct
3 Correct 69 ms 604 KB Output is correct
4 Correct 192 ms 716 KB Output is correct
5 Correct 53 ms 600 KB Output is correct
6 Correct 72 ms 604 KB Output is correct
7 Correct 138 ms 600 KB Output is correct
8 Correct 43 ms 604 KB Output is correct
9 Correct 84 ms 676 KB Output is correct
10 Correct 211 ms 604 KB Output is correct
11 Correct 207 ms 600 KB Output is correct
12 Correct 207 ms 600 KB Output is correct
13 Correct 204 ms 600 KB Output is correct
14 Correct 224 ms 604 KB Output is correct
15 Correct 223 ms 604 KB Output is correct
16 Correct 109 ms 700 KB Output is correct
17 Correct 129 ms 604 KB Output is correct
18 Correct 125 ms 600 KB Output is correct
19 Correct 23 ms 640 KB Output is correct
20 Incorrect 85 ms 604 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 672 KB Output is correct
2 Correct 9 ms 604 KB Output is correct
3 Correct 69 ms 604 KB Output is correct
4 Correct 192 ms 716 KB Output is correct
5 Correct 53 ms 600 KB Output is correct
6 Correct 72 ms 604 KB Output is correct
7 Correct 138 ms 600 KB Output is correct
8 Correct 43 ms 604 KB Output is correct
9 Correct 84 ms 676 KB Output is correct
10 Correct 211 ms 604 KB Output is correct
11 Correct 207 ms 600 KB Output is correct
12 Correct 207 ms 600 KB Output is correct
13 Correct 204 ms 600 KB Output is correct
14 Correct 224 ms 604 KB Output is correct
15 Correct 223 ms 604 KB Output is correct
16 Incorrect 176 ms 604 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 50.0

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