oj.uz

Submission #551899

# Submission time Handle Problem Language Result Execution time Memory
551899 2022-04-21T20:54:49 Z Antekb Copy and Paste 3 (JOI22_copypaste3) C++14
0 / 100
 603 ms 33880 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
using ll = long long;
const int N=2505;
ll dp[N][N];
int main(){
	int n;
	cin>>n;
	string s;
	cin>>s;
	int A, B, C;
	cin>>A>>B>>C;
	for(int l=1; l<=n; l++){
		for(int i=0; i<=n-l; i++){
			dp[i][i+l-1]=max({dp[i][i+l-1], dp[i][i+l-2], dp[i+1][i+l-1]});
		}
		ll pot=1;
		int bas=124338541;
		ll hasz=0;
		for(int i=0; i<l; i++){
			pot*=bas;	
		}
		vector<pair<ll, int> > V;
		for(int i=0; i<n; i++){
			hasz*=bas;
			hasz+=s[i];
			if(i>=l)hasz-=pot*ll(s[i-l]);
			if(i>=l-1)V.push_back({hasz, i});
		}
		vector<int> par(n);
		sort(V.begin(), V.end());
		for(int i=0; i<=n-l; i++){
			//cout<<V[i].st<<","<<V[i].nd<<" ";
			int t=upper_bound(V.begin(), V.end(), make_pair(V[i].st, V[i].nd-l))-V.begin();
			t--;
			if(t>=0 && V[t].st==V[i].st)par[V[i].nd]=V[t].nd;
		}
		//cout<<"\n";
		for(int i=0; i<n; i++){
			//cout<<i<<" "<<par[i]<<"\n";
			int j=2, p=par[i];
			while(p){
				//if(l==3 && i==7 && p==4)cout<<"a"<<" "<<(j-1)*l*1ll*A<<" "<<dp[p-l+1][p]<<" "<<B+j*1ll*C<<"\n";
				dp[p-l+1][i]=max(dp[p-l+1][i], (j-1)*l*1ll*A+dp[p-l+1][p]-B-j*1ll*C);
				p=par[p];
				j++;
			}
		}
	}
	for(int i=0; i<n; i++){
		for(int j=i; j<n; j++){
			//cout<<A*(j-i+1)-dp[i][j]<<" \n"[j==n-1];
		}
	}
	cout<<A*1ll*n-dp[0][n-1];
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 310 ms 20820 KB Output is correct
4 Correct 336 ms 23688 KB Output is correct
5 Correct 439 ms 26708 KB Output is correct
6 Correct 593 ms 30176 KB Output is correct
7 Correct 585 ms 33876 KB Output is correct
8 Correct 592 ms 33880 KB Output is correct
9 Incorrect 603 ms 33856 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -