Submission #1092008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092008		_rain_	Visiting Singapore (NOI20_visitingsingapore)	C++14	29 / 100	278 ms	1108 KiB

VisitingSingapore

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define fixbug false
 
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 dpcot[maxn+2] , tamcot[maxn+2] , cot[maxn+2];
	ll dgcheo[maxn+2] , tamcheo[maxn+2];
	ll dp[maxn+2] , f[maxn+2];
	ll ngang[maxn+2]={},tamngang[maxn+2];
	void main_code(){
		memset(dpcot,-0x3f,sizeof dpcot);
		memset(dgcheo,-0x3f,sizeof dgcheo);
		memset(dp,-0x3f,sizeof dp);
		memset(ngang,-0x3f,sizeof ngang);
		for (int i = 0; i <= n; ++i) dp[i] = 0;
		ll ans = -INF;
		for (int layer = 1; layer <= m; ++layer) // T for 
		{
			if (fixbug){
				cout << "(DEBUG)\n";
			}
			for (int i = 0; i <= n; ++i){
				tamcheo[i] = dgcheo[i];
				tamcot[i] = dpcot[i];
				tamngang[i] = ngang[i];
				f[i] = dp[i];
				ngang[i] = dpcot[i] = dgcheo[i] = dp[i] = -INF;
			}
			for (int i = 1; i <= n; ++i) // S for 
			{
				if(s[i]==t[layer])
				{
					dp[i] = max({
						f[i - 1],
						tamcot[i - 1] ,	
						cot[i],
						tamcheo[i-1],
						ngang[i-1]
					}) + v[t[layer]];	
				} 	
				dpcot[i] = max({
					dp[i-1] + sub(1,1,0,0),
					max(tamcot[i],dpcot[i-1]) + sub(0,1,0,0),
					f[i] + sub(1,1,0,0)
				});
				dgcheo[i] = max({ 	
					f[i-1] + sub(1,1,1,1),
					tamcheo[i-1] + sub(0,1,0,1)
				});
				ngang[i] = max({
					ngang[i-1] + sub(0,0,0,1),
					tamcheo[i-1] + sub(0,1,0,1),
					dgcheo[i-1] + sub(0,1,0,0),
					f[i-1] + sub(1,1,1,1),
					tamngang[i] + sub(0,0,0,1)
				});
				if (layer==1) cot[i] += sub(1,1,0,0); else cot[i] += sub(0,1,0,0);
				if (layer==m){
					ans = max({
						ans,dp[i],dgcheo[i],dpcot[i],ngang[i]
					});
				}
				if (fixbug){
					cout << layer << " -- " << i << '\n';
					cout << ngang[i] << ' ' << dpcot[i] << ' ' << dgcheo[i] << ' ' << dp[i] << '\n';
				}
			}
		}
		// for (int i = 1; i <= n; ++i) ans = max(ans,dp[i]);
		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: 4 / 4
• Subtask 2: 6 / 6
• Subtask 3: 12 / 12
• Subtask 4: 7 / 7
• Subtask 5: 0 / 8
• Subtask 6: 0 / 13
• Subtask 7: 0 / 50