oj.uz

Submission #776926

# Submission time Handle Problem Language Result Execution time Memory
776926 2023-07-08T11:58:04 Z aZvezda Copy and Paste 3 (JOI22_copypaste3) C++14
1 / 100
 3000 ms 470468 KB 
#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][2];
ll ind[MAX_N][MAX_N], cnt;

const ll LOG = 14;
ll par[MAX_N * MAX_N][LOG], start[MAX_N * MAX_N], d[MAX_N * MAX_N];
vector<ll> g[MAX_N * MAX_N];

void dfs(ll x, ll p) {
	par[x][0] = p;
	for(ll i = 1; i < LOG; i ++) {
		par[x][i] = par[par[x][i - 1]][i - 1];
	}
	d[x] = d[p] + 1;
	for(const auto it : g[x]) {
		dfs(it, x);
	}
}

ll lft(ll l, ll r, ll len) {
	ll id = ind[r - len + 1][len];
	ll ret = d[id];
	for(ll i = LOG - 1; i >= 0; i --) {
		if(start[par[id][i]] >= l) {
			id = par[id][i];
		}	
	}
	return ret - d[id] + 1;
}


ll solve(ll l, ll r, bool clip) {
	if(!clip) { return (r - l + 1) * a; }
	if(dp[l][r][clip] != -1) { return dp[l][r][clip]; }
	if(l == r) { return a; }
	ll &ans = dp[l][r][clip];
	ans = (r - l + 1) * a;
	ans = min(ans, solve(l, r - 1, true) + a);
	ans = min(ans, solve(l, r - 1, false) + a);
	for(ll len = 1; len <= (r - l + 1); len ++) {
		ll cnt = lft(l, r, len);
		ll total = 
			solve(r - len + 1, r, true) + b + 
			cnt * c + (r - l + 1 - cnt * len) * a;
		ans = min(ans, total);
	}	
	return ans;
}

const ll mod1 = 1e9 + 7, mod2 = 1e9 + 9;
const ll base1 = 27, base2 = 37;
ll state[MAX_N];

signed main() {

	cin >> n >> str >> a >> b >> c;

	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 + now
			) % mod1;
			hsh2 = (
				(hsh2 - pw2 * (ll)(str[i - 1] - 'a' + 1ll)) 
				% mod2 * base2 + now
			) % mod2;
			state[i] = hsh1 + hsh2 * mod1;
		}
		map<ll, ll> mp;
		for(ll i = 0; i + len - 1 < n; i ++) {
			ind[i][len] = ++ cnt;
			start[cnt] = i;
			if(i - len >= 0) {
				mp[state[i - len]] = ind[i - len][len];
			}
			g[mp[state[i]]].push_back(ind[i][len]);
		}
	}

	start[0] = -mod1;
	dfs(0, 0);

	for(ll i = 0; i < n; i ++) {
		for(ll j = 0; j < n; j ++) {
			dp[i][j][0] = dp[i][j][1] = -1;
		}		
	}

	cout << solve(0, n - 1, true) << endl;
	
    return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 148248 KB Output is correct
2 Correct 64 ms 148252 KB Output is correct
3 Correct 64 ms 148188 KB Output is correct
4 Correct 63 ms 148296 KB Output is correct
5 Correct 66 ms 148240 KB Output is correct
6 Correct 63 ms 148228 KB Output is correct
7 Correct 67 ms 148276 KB Output is correct
8 Correct 72 ms 148208 KB Output is correct
9 Correct 63 ms 148172 KB Output is correct
10 Correct 62 ms 148212 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 148324 KB Output is correct
2 Correct 63 ms 148276 KB Output is correct
3 Execution timed out 3066 ms 470468 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 148248 KB Output is correct
2 Correct 64 ms 148252 KB Output is correct
3 Correct 64 ms 148188 KB Output is correct
4 Correct 63 ms 148296 KB Output is correct
5 Correct 66 ms 148240 KB Output is correct
6 Correct 63 ms 148228 KB Output is correct
7 Correct 67 ms 148276 KB Output is correct
8 Correct 72 ms 148208 KB Output is correct
9 Correct 63 ms 148172 KB Output is correct
10 Correct 62 ms 148212 KB Output is correct
11 Correct 79 ms 148276 KB Output is correct
12 Correct 72 ms 148428 KB Output is correct
13 Correct 74 ms 148460 KB Output is correct
14 Correct 70 ms 148296 KB Output is correct
15 Correct 73 ms 148396 KB Output is correct
16 Correct 70 ms 148356 KB Output is correct
17 Correct 70 ms 148236 KB Output is correct
18 Correct 70 ms 148176 KB Output is correct
19 Correct 69 ms 148336 KB Output is correct
20 Correct 69 ms 148212 KB Output is correct
21 Correct 75 ms 148556 KB Output is correct
22 Correct 69 ms 148596 KB Output is correct
23 Correct 77 ms 148528 KB Output is correct
24 Correct 72 ms 148504 KB Output is correct
25 Correct 71 ms 148556 KB Output is correct
26 Correct 70 ms 148576 KB Output is correct
27 Correct 71 ms 148512 KB Output is correct
28 Incorrect 71 ms 148552 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 148248 KB Output is correct
2 Correct 64 ms 148252 KB Output is correct
3 Correct 64 ms 148188 KB Output is correct
4 Correct 63 ms 148296 KB Output is correct
5 Correct 66 ms 148240 KB Output is correct
6 Correct 63 ms 148228 KB Output is correct
7 Correct 67 ms 148276 KB Output is correct
8 Correct 72 ms 148208 KB Output is correct
9 Correct 63 ms 148172 KB Output is correct
10 Correct 62 ms 148212 KB Output is correct
11 Correct 79 ms 148276 KB Output is correct
12 Correct 72 ms 148428 KB Output is correct
13 Correct 74 ms 148460 KB Output is correct
14 Correct 70 ms 148296 KB Output is correct
15 Correct 73 ms 148396 KB Output is correct
16 Correct 70 ms 148356 KB Output is correct
17 Correct 70 ms 148236 KB Output is correct
18 Correct 70 ms 148176 KB Output is correct
19 Correct 69 ms 148336 KB Output is correct
20 Correct 69 ms 148212 KB Output is correct
21 Correct 75 ms 148556 KB Output is correct
22 Correct 69 ms 148596 KB Output is correct
23 Correct 77 ms 148528 KB Output is correct
24 Correct 72 ms 148504 KB Output is correct
25 Correct 71 ms 148556 KB Output is correct
26 Correct 70 ms 148576 KB Output is correct
27 Correct 71 ms 148512 KB Output is correct
28 Incorrect 71 ms 148552 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 148248 KB Output is correct
2 Correct 64 ms 148252 KB Output is correct
3 Correct 64 ms 148188 KB Output is correct
4 Correct 63 ms 148296 KB Output is correct
5 Correct 66 ms 148240 KB Output is correct
6 Correct 63 ms 148228 KB Output is correct
7 Correct 67 ms 148276 KB Output is correct
8 Correct 72 ms 148208 KB Output is correct
9 Correct 63 ms 148172 KB Output is correct
10 Correct 62 ms 148212 KB Output is correct
11 Correct 79 ms 148276 KB Output is correct
12 Correct 72 ms 148428 KB Output is correct
13 Correct 74 ms 148460 KB Output is correct
14 Correct 70 ms 148296 KB Output is correct
15 Correct 73 ms 148396 KB Output is correct
16 Correct 70 ms 148356 KB Output is correct
17 Correct 70 ms 148236 KB Output is correct
18 Correct 70 ms 148176 KB Output is correct
19 Correct 69 ms 148336 KB Output is correct
20 Correct 69 ms 148212 KB Output is correct
21 Correct 75 ms 148556 KB Output is correct
22 Correct 69 ms 148596 KB Output is correct
23 Correct 77 ms 148528 KB Output is correct
24 Correct 72 ms 148504 KB Output is correct
25 Correct 71 ms 148556 KB Output is correct
26 Correct 70 ms 148576 KB Output is correct
27 Correct 71 ms 148512 KB Output is correct
28 Incorrect 71 ms 148552 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 148248 KB Output is correct
2 Correct 64 ms 148252 KB Output is correct
3 Correct 64 ms 148188 KB Output is correct
4 Correct 63 ms 148296 KB Output is correct
5 Correct 66 ms 148240 KB Output is correct
6 Correct 63 ms 148228 KB Output is correct
7 Correct 67 ms 148276 KB Output is correct
8 Correct 72 ms 148208 KB Output is correct
9 Correct 63 ms 148172 KB Output is correct
10 Correct 62 ms 148212 KB Output is correct
11 Correct 63 ms 148324 KB Output is correct
12 Correct 63 ms 148276 KB Output is correct
13 Execution timed out 3066 ms 470468 KB Time limit exceeded
14 Halted 0 ms 0 KB -