Submission #776971

#	Time	Username	Problem	Language	Result	Execution time	Memory
776971		aZvezda	Copy and Paste 3 (JOI22_copypaste3)	C++14	100 / 100	412 ms	49596 KiB

copypaste3

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define cerr if(false)cerr
 
const ll MAX_N = 2510;
ll n, a, b, c;
string str;
 
ll dp[MAX_N][MAX_N];
 
const ll mod1 = 1e9 + 7, mod2 = 2e9 + 9;
const ll base1 = 37, base2 = 127;
ll state[MAX_N];
int par[MAX_N];

template<class T, class T2> bool chkmin(T &a, const T2 &b) { return a > b ? a = b, 1 : 0; }

signed main() {
 
	cin >> n >> str >> a >> b >> c;
 
	for(ll i = 0; i < n; i ++) {
		for(ll j = 0; j < n; j ++) {
			dp[i][j] = (j - i + 1ll) * a;
		}		
	}
 
	for(ll len = 1; len <= n; len ++) {
		ll hsh1 = 0, hsh2 = 0;		
		ll pw1 = 1, pw2 = 1;
		for(ll i = 0; i < len; i ++) {
			ll now = str[i] - 'a' + 1;
			hsh1 = (hsh1 * base1 + now) % mod1;
			hsh2 = (hsh2 * base2 + now) % mod2;
			if(i != 0) {
				pw1 = (pw1 * base1) % mod1;
				pw2 = (pw2 * base2) % mod2;
			}
		}
		state[0] = hsh1 + hsh2 * mod1;
		for(ll i = 1; i + len - 1 < n; i ++) {
			ll now = str[i + len - 1] - 'a' + 1;
			hsh1 = (
				(hsh1 - pw1 * (ll)(str[i - 1] - 'a' + 1ll)) 
				% mod1 * base1 % mod1 + mod1 + now
			) % mod1;
			hsh2 = (
				(hsh2 - pw2 * (ll)(str[i - 1] - 'a' + 1ll)) 
				% mod2 * base2 % mod2 + mod2 + now
			) % mod2;
			state[i] = hsh1 + hsh2 * mod1;
		}
		map<ll, ll> mp;
		for(ll i = 0; i + len - 1 < n; i ++) {
			chkmin(dp[i][i + len - 1], dp[i + 1][i + len - 1] + a);
			chkmin(dp[i][i + len - 1], dp[i][i + len - 2] + a);
			if(i - len >= 0) {
				mp[state[i - len]] = i - len;
			}
			if(mp.find(state[i]) != mp.end()) {
				par[i] = mp[state[i]];
			} else {
				par[i] = -1;
			}
			int curr = par[i], cnt = 2;
			while(curr != -1) {
				int r = i + len - 1;
				dp[curr][r] = min(dp[curr][r], dp[i][i + len - 1] + (r - curr + 1 - cnt * len) * a + b + cnt * c);
				curr = par[curr];
				cnt ++;
			}
		}
	}

	cout << dp[0][n - 1] << endl;

	return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 5 / 5
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 32 / 32
• Subtask 6: 38 / 38