oj.uz

Submission #710866

# Submission time Handle Problem Language Result Execution time Memory
710866 2023-03-16T03:11:40 Z minhcool Copy and Paste 3 (JOI22_copypaste3) C++17
1 / 100
 1055 ms 918360 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define hash hashy


typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 2e3 + 5;
const int mod = 1e9 + 7, oo = 1e18 + 7;

const int md1 = 1e9 + 87, md2 = 1e9 + 123;

int n, a, b, c;
string s;

int dp[N][N];

int mx[N][N];

int sparse[N][N][15];

ii hash[N];

ii pw26[N];

ii get(int l, int r){
	int temp1 = (hash[r].fi - hash[l - 1].fi * pw26[r - l + 1].fi + md1 * md1) % md1;
	int temp2 = (hash[r].se - hash[l - 1].se * pw26[r - l + 1].se + md2 * md2) % md2;
	return {temp1, temp2};
}

void process(){
    cin >> n >> s >> a >> b >> c;
	s = '*' + s;
	pw26[0] = {1, 1};
	for(int i = 1; i <= n; i++){
		hash[i].fi = (hash[i - 1].fi * 31 + s[i] - 'a') % md1;
		hash[i].se = (hash[i - 1].se * 37 + s[i] - 'a') % md2;
		pw26[i].fi = (pw26[i - 1].fi * 31) % md1;
		pw26[i].se = (pw26[i - 1].se * 37) % md2;
 	}
	for(int i = 1; i <= n; i++){
		for(int j = i + 1; j <= n; j++){
			if(s[i] != s[j]){
				mx[i][j] = mx[j][i] = 0;
				continue;
			}
			int le = i, ri = n;
			while(le < ri){
				int mid = (le + ri + 1) >> 1;
				if((mid + (j - i)) > n) ri = mid - 1;
				ii temp1 = get(i, mid), temp2 = get(j, mid + (j - i));
				if(temp1 == temp2) le = mid;
				else ri = mid - 1;
			}
			mx[i][j] = mx[j][i] = (le - i + 1);
		//	cout << i << " " << j << " " << mx[i][j] << "\n";
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = i; j <= n; j++) sparse[i][j][0] = mx[i][j];
		for(int j = 1; j <= 13; j++){
			for(int k = j; (k + (1LL << j) - 1) <= n; k++){
				sparse[i][k][j] = max(sparse[i][k][j - 1], sparse[i][k + (1LL << (j - 1))][j - 1]);
			}
		}
	}
	for(int i = 1; i <= n; i++) dp[i][i] = a;
	for(int le = n; le >= 1; le--){
		for(int ri = le + 1; ri <= n; ri++) dp[le][ri] = oo;
		for(int ri = le; ri <= n; ri++){
			dp[le][ri] = min(dp[le][ri], min(dp[le][ri - 1], dp[le + 1][ri]) + a);
			vector<int> pos;
			pos.pb(le);
			int itr = ri + 1;
			while(itr <= n){
				for(int i = 13; i >= 0; i--){
					if((itr + (1LL << i) - 1) > n) continue;
					if(sparse[le][itr][i] < (ri - le + 1)) itr += (1LL << i);
				}
				if(sparse[le][itr][0] < (ri - le + 1)) break;
				pos.pb(itr);
				itr += (ri - le + 1);
			}
			int cnt = 0;
			for(auto it : pos){
				//cout << "OK" << le << " " << ri << " " << it << "\n";
				cnt++;
				int rem = ((it + ri - le) - le + 1) - (ri - le + 1) * cnt;
				if(cnt > 1) dp[le][it + (ri - le)] = min(dp[le][it + (ri - le)], dp[le][ri] + b + c * cnt + a * rem);
			}
		}
		for(int ri = le; ri <= n; ri++){
			//cout << le << " " << ri << " " << dp[le][ri] << "\n";
		}
	}
	cout << dp[1][n] << "\n";
}

signed main(){
    ios_base::sync_with_stdio(0);
    //freopen("KEK.inp", "r", stdin);
    //freopen("KEK.out", "w", stdout);
    cin.tie(0);
    process();
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 328 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 328 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 945 ms 451484 KB Output is correct
4 Correct 1055 ms 522272 KB Output is correct
5 Runtime error 877 ms 918360 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 328 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 328 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 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 596 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Incorrect 1 ms 596 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 328 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 328 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 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 596 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Incorrect 1 ms 596 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 328 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 328 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 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 596 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Incorrect 1 ms 596 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 328 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 328 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 945 ms 451484 KB Output is correct
14 Correct 1055 ms 522272 KB Output is correct
15 Runtime error 877 ms 918360 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -