oj.uz

답안 #710867

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
710867 2023-03-16T03:12:13 Z minhcool Copy and Paste 3 (JOI22_copypaste3) C++17
1 / 100
 1543 ms 726052 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 = 3e3 + 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 404 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 332 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 945 ms 460856 KB Output is correct
4 Correct 1047 ms 536268 KB Output is correct
5 Correct 1233 ms 624368 KB Output is correct
6 Incorrect 1543 ms 726052 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 404 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 332 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 340 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 404 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 332 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 340 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 404 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 332 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 340 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 404 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 332 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 336 KB Output is correct
13 Correct 945 ms 460856 KB Output is correct
14 Correct 1047 ms 536268 KB Output is correct
15 Correct 1233 ms 624368 KB Output is correct
16 Incorrect 1543 ms 726052 KB Output isn't correct
17 Halted 0 ms 0 KB -