Submission #679729

#	Time	Username	Problem	Language	Result	Execution time	Memory
679729		DP_196	Visiting Singapore (NOI20_visitingsingapore)	C++14	42 / 100	126 ms	262144 KiB

VisitingSingapore

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define MASK(i) ((1LL) << (i))
#define all(x) x.begin(), x.end()
#define BIT(x, i) ((x) >> (i) & (1LL))
#define dbg(...) cerr << "#" << __LINE__ << ":[" << #__VA_ARGS__ \
<< "] = [" ,DBG(__VA_ARGS__)

string to_string(const string& s) { return '"' + s + '"'; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
        cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...);
}

template <class T>
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b) : 0); }
template <class T>
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b) : 0); }

const int MAXN = 1e5 + 6;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int k, n, m, a, b, v[5005], s[5005], t[5005];
int g[5005][5005], f[105][105], dp[5005][5005][2][2];

void sub1() {
	if (m <= n) return (void) (cout << (v[1] * m));
	cout << v[1] * n + (a + (m - n) * b);
}

void sub2() {
	int res = m * b;

	for (int j = 0; j <= m; j++) g[0][j] = j * b;
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= m; j++) {
			g[i][j] = max(g[i - 1][j], g[i][j - 1]) + b;
			if (s[i] == t[j]) maximize(g[i][j], g[i - 1][j - 1] + v[s[i]]);
			maximize(res, g[i][j] + (m - j) * b);
		}
	
	cout << res;
}

void sub6() {	
	int res = a + m * b;
	for (int j = 0; j <= m; j++) f[0][j] = j * b;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (s[i] != t[j]) continue;
			f[i][j] = v[s[i]] + (j > 1 ? a + (j - 1) * b : 0);
			for (int x = 1; x < i; x++)
				for (int y = 1; y < j; y++)
					if (s[x] == t[y]) maximize(f[i][j], v[s[i]] + f[x][y] + 
						(j - y >= 2 ? a + (j - y - 1) * b : 0) + (i - x >= 2 ? a + (i - x - 1) * b : 0));
			maximize(res, f[i][j] + (m != j ? a + (m - j) * b : 0));
		}
	}
	
	cout << res;
}     

void sub4() {
	int res = a;
	
	memset(dp, -0x3f, sizeof (dp));
	dp[0][0][0][0] = 0;
 	for (int i = 0; i <= m; i++) {
		dp[0][i][0][1] = a;
		dp[0][i][0][0] = a;
	}
	
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= m; j++) { 
			dp[i][j][0][0] = max({dp[i - 1][j][0][0], dp[i][j - 1][0][0], dp[i - 1][j - 1][1][1]});
			dp[i][j][0][1] = max(dp[i - 1][j][0][1], dp[i - 1][j][1][1]);
			dp[i][j][1][0] = max(dp[i][j - 1][1][0], dp[i][j - 1][1][1]);
			
			if (s[i] == t[j]) {
				dp[i][j][1][1] = v[s[i]] + (j > 1 ? a : 0);
				maximize(dp[i][j][1][1], dp[i - 1][j - 1][0][0] + 2 * a + v[s[i]]);
				maximize(dp[i][j][1][1], dp[i - 1][j - 1][0][1] + a + v[s[i]]);
				maximize(dp[i][j][1][1], dp[i - 1][j - 1][1][0] + a + v[s[i]]);
				maximize(dp[i][j][1][1], dp[i - 1][j - 1][1][1] + v[s[i]]);
			}
			
			maximize(res, dp[i][j][1][1] + (m - j >= 1 ? a : 0));
		}
	
	cout << res;
}                     

void solve() {
	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 (k == 1) sub1();
	else if (a == 0) sub2();
	else if (b == 0) sub4();
	else if (n <= 100 && m <= 100) sub6();
}

#define TASK "FUNTOUR"
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
   	//freopen(TASK".inp", "r", stdin);
   	//freopen(TASK".out", "w", stdout);

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

    return 0;
}
//612

• Subtask 1: 4 / 4
• Subtask 2: 6 / 6
• Subtask 3: 12 / 12
• Subtask 4: 7 / 7
• Subtask 5: 0 / 8
• Subtask 6: 13 / 13
• Subtask 7: 0 / 50