Submission #1193110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193110		loom	Visiting Singapore (NOI20_visitingsingapore)	C++20	100 / 100	162 ms	636 KiB

VisitingSingapore

#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
#define nl '\n'

int ldp[5001][2][2];
int  dp[5001][2][2];

inline void solve(){
	int k, n, m, a, b;
	cin>>k>>n>>m>>a>>b;
	a *= -1, b *= -1;

	int v[k+1], s[n+1], t[m+1];
	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];

	for(int i=0; i<=m; i++){
		ldp[i][0][0] = -2*a - i*b;
		ldp[i][0][1] = ldp[i][1][0] = ldp[i][1][1] = -inf;
	}

	int ans = -a - m*b;
	for(int i=1; i<=n; i++){
		dp[0][0][0] = -2*a - i*b;
		dp[0][0][1] = dp[0][1][0] = dp[0][1][1] = -inf;

		for(int j=1; j<=m; j++){
			dp[j][0][0] = max({ldp[j-1][0][0], ldp[j-1][0][1] - a, ldp[j-1][1][0] - a, ldp[j-1][1][1] - 2*a}) - 2*b;

			dp[j][0][1] = max(ldp[j][0][1], ldp[j][1][1] - a) - b;

			dp[j][1][0] = max(dp[j-1][1][0], dp[j-1][1][1] - a) - b;

			dp[j][1][1] = -inf;
			if(s[i] == t[j]) dp[j][1][1] = v[s[i]] + max({ldp[j-1][0][0], ldp[j-1][0][1], ldp[j-1][1][0], ldp[j-1][1][1], (j == 1 ? 0 : -a) - (j-1)*b});
			ans = max(ans, dp[j][1][1] - (j == m ? 0 : a) - (m-j)*b);
		}

		for(int j=0; j<=m; j++) for(int k=0; k<2; k++) for(int l=0; l<2; l++) ldp[j][k][l] = dp[j][k][l];
	}

	cout<<ans;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);cout.tie(NULL);

	int t = 1;
	//cin>>t;
	while(t--) solve();

	return 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