Submission #1091870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091870		_rain_	Visiting Singapore (NOI20_visitingsingapore)	C++14	10 / 100	121 ms	262144 KiB

VisitingSingapore

#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 / 4
• Subtask 2: 6 / 6
• Subtask 3: 0 / 12
• Subtask 4: 0 / 7
• Subtask 5: 0 / 8
• Subtask 6: 0 / 13
• Subtask 7: 0 / 50