Submission #1092351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092351		_rain_	Visiting Singapore (NOI20_visitingsingapore)	C++14	100 / 100	460 ms	860 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;
	}
	const ll INF = (ll)1e18+7;
	ll dp[maxn+2][2][2]; // FOR the layer , SKIP S , SKIP T
	ll tam[maxn+2][2][2];
	void main_code(){
		memset(dp,-0x3f,sizeof dp);
		ll ans = -INF;
		for (int i = 0; i <= n; ++i) dp[i][1][1] = 0; // START state
		for (int layer = 1; layer <= m; ++layer){
			for (int i = 0; i <= n; ++i){
				for (int match1 = 0; match1 <= 1; ++match1){
					for (int match2 = 0; match2 <= 1; ++match2){
						tam[i][match1][match2] = dp[i][match1][match2];
						dp[i][match1][match2] = -INF;
					}
				}
			}
			for (int i = 0; i <= n; ++i){
				for (int match1 = 0; match1 <= 1; ++match1) 
				for (int match2 = 0; match2 <= 1; ++match2)
				{
					if (s[i]==t[layer]&&i-1>=0){
						dp[i][1][1] = max({
							dp[i][1][1] , 
							tam[i - 1][match1][match2] + v[t[layer]]
						});
					}
					// SKIP S
						if (i - 1 >= 0)
							dp[i][0][match2] = max({
								dp[i][0][match2] , 
								dp[i-1][match1][match2] + B + A * match1
							});
					// SKIP T
						dp[i][match1][0] = max({
							dp[i][match1][0] , 
							tam[i][match1][match2] + B + A * match2
						});	
				}
			}
		}
		for (int i = 1; i <= n; ++i){
			for (int match1 = 0; match1 <= 1; ++match1){
				for (int match2 = 0; match2 <= 1; ++match2){
					// cout << dp[i][match1][match2] << ' ' << i << ' ' << match1 << ' ' << match2 << '\n';
					ans = max(ans , dp[i][match1][match2]);
				}
			}
		}
		cout << ans << '\n';
	}
}
 
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: 8 / 8
• Subtask 6: 13 / 13
• Subtask 7: 50 / 50