oj.uz

Submission #1091870

# Submission time Handle Problem Language Result Execution time Memory
1091870 2024-09-22T12:08:42 Z _rain_ Visiting Singapore (NOI20_visitingsingapore) C++14
10 / 100
 121 ms 262144 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 subtask1{
	bool check(){
		return K==1;
	}
	void main_code(){
		if (n < m){
			cout << n * v[1] + B * (m - n) + A;
			exit(0);
		}
		cout << m * v[1] << '\n';
		exit(0);	
	}
}
namespace subtask2{
	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][maxn+2][2] , tam[maxn+2][maxn+2][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][0][1] = 0;
		}
		ll ans = -INF;
		for (int layer = 1; layer <= m; ++layer) // T for 
		{
			for (int i = 1; i <= n; ++i) // S for 
			{
				if (s[i] == t[layer])
				{
					dp[i][layer][1] = max({
						dp[i-1][layer-1][1] , dp[i-1][layer-1][0] , cot[i] , tam[i-1][layer][0]
					}) + v[t[layer]];
				}
				dp[i][layer][0] = max({
					dp[i-1][layer-1][1] + sub(1,1,1,1),
					dp[i-1][layer-1][0] + sub(0,1,0,1),
					dp[i][layer-1][0] + sub(0,0,0,1),
					dp[i][layer-1][1] + sub(0,0,1,1),
					dp[i-1][layer][0] + sub(0,1,0,0),
					dp[i-1][layer][1] + sub(1,1,0,0)
				});
				tam[i][layer][0] = max({
					dp[i-1][layer-1][1] + sub(1,1,1,1),
					dp[i-1][layer-1][0] + sub(0,1,0,1),
					dp[i][layer-1][0] + sub(0,0,0,1),
					dp[i][layer-1][1] + sub(0,0,1,1),
					tam[i-1][layer][0] + 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);

				// if (layer==m)
				// 	cout << dp[i][layer][1] << ' ' << dp[i][layer][0] << ' ' << i  << ' ' << layer << '\n';
			}
		}
		for (int i = 1; i <= n; ++i) ans = max({ans , dp[i][m][0],dp[i][m][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 (subtask1::check()){
		subtask1::main_code();
		exit(0);
	}
	if (subtask2::check()){
		subtask2::main_code();
		exit(0);
	}
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 464 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 464 KB Output is correct
5 Correct 0 ms 460 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 111 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 111 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 111 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 121 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 464 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 460 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 464 KB Output is correct
15 Correct 0 ms 460 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Runtime error 111 ms 262144 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -