Submission #776925

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
776925	2023-07-08T11:57:39 Z	aZvezda	Copy and Paste 3 (JOI22_copypaste3)	C++14	1 / 100	145 ms	127132 KB

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][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];

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	Memory	Grader output
1	Correct	340 KB	Output is correct
2	Correct	340 KB	Output is correct
3	Correct	340 KB	Output is correct
4	Correct	340 KB	Output is correct
5	Correct	340 KB	Output is correct
6	Correct	340 KB	Output is correct
7	Correct	340 KB	Output is correct
8	Correct	340 KB	Output is correct
9	Correct	340 KB	Output is correct
10	Correct	340 KB	Output is correct

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	468 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Runtime error	145 ms	127132 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-

Subtask #3
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	1 ms	468 KB	Output is correct
13	Correct	1 ms	468 KB	Output is correct
14	Correct	0 ms	468 KB	Output is correct
15	Correct	1 ms	596 KB	Output is correct
16	Correct	0 ms	468 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	0 ms	468 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	1 ms	596 KB	Output is correct
22	Correct	1 ms	596 KB	Output is correct
23	Correct	1 ms	724 KB	Output is correct
24	Correct	1 ms	596 KB	Output is correct
25	Correct	1 ms	596 KB	Output is correct
26	Correct	1 ms	596 KB	Output is correct
27	Correct	1 ms	724 KB	Output is correct
28	Incorrect	1 ms	724 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #4
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	1 ms	468 KB	Output is correct
13	Correct	1 ms	468 KB	Output is correct
14	Correct	0 ms	468 KB	Output is correct
15	Correct	1 ms	596 KB	Output is correct
16	Correct	0 ms	468 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	0 ms	468 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	1 ms	596 KB	Output is correct
22	Correct	1 ms	596 KB	Output is correct
23	Correct	1 ms	724 KB	Output is correct
24	Correct	1 ms	596 KB	Output is correct
25	Correct	1 ms	596 KB	Output is correct
26	Correct	1 ms	596 KB	Output is correct
27	Correct	1 ms	724 KB	Output is correct
28	Incorrect	1 ms	724 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #5
0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	1 ms	468 KB	Output is correct
13	Correct	1 ms	468 KB	Output is correct
14	Correct	0 ms	468 KB	Output is correct
15	Correct	1 ms	596 KB	Output is correct
16	Correct	0 ms	468 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	0 ms	468 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	1 ms	596 KB	Output is correct
22	Correct	1 ms	596 KB	Output is correct
23	Correct	1 ms	724 KB	Output is correct
24	Correct	1 ms	596 KB	Output is correct
25	Correct	1 ms	596 KB	Output is correct
26	Correct	1 ms	596 KB	Output is correct
27	Correct	1 ms	724 KB	Output is correct
28	Incorrect	1 ms	724 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #6
0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	468 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Runtime error	145 ms	127132 KB	Execution killed with signal 11
14	Halted	0 ms	0 KB	-

Submission #776925

Compilation message

Subtask #1 1.0 / 1.0

Subtask #2 0 / 5.0

Subtask #3 0 / 14.0

Subtask #4 0 / 10.0

Subtask #5 0 / 32.0

Subtask #6 0 / 38.0

Subtask #1
1.0 / 1.0

Subtask #2
0 / 5.0

Subtask #3
0 / 14.0

Subtask #4
0 / 10.0

Subtask #5
0 / 32.0

Subtask #6
0 / 38.0