oj.uz

Submission #713952

# Submission time Handle Problem Language Result Execution time Memory
713952 2023-03-23T10:03:39 Z 089487 Copy and Paste 3 (JOI22_copypaste3) C++14
1 / 100
 1370 ms 141208 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
#define int long long
#define quick ios::sync_with_stdio(0);cin.tie(0);
#define rep(x,a,b) for(int x=a;x<=b;x++)
#define repd(x,a,b) for(int x=a;x>=b;x--)
#define lowbit(x) (x&-x)
#define sz(x) (int)(x.size())
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define mp make_pair
#define eb emplace_back
using namespace std;
typedef pair<int,int> pii;
void debug(){
    cout<<"\n";
}
template <class T,class ... U >
void debug(T a, U ... b){
    cout<<a<<" ",debug(b...);
}
const int N=2e2+7;
const int INF=1e18;
const int Mod=1e9+7;
int dp[N][N][N];
int pref[N];
int d2[N][N];
int p;
int px[N];
string s;
void build(int n){
	pref[0]=0;
	rep(i,1,n){
		pref[i]=pref[i-1]*p%Mod+s[i-1]-'a'+1;
		pref[i]%=Mod;
	}
}
int q(int l,int r){
	return (pref[r]-pref[l-1]*px[r-l+1]%Mod+Mod)%Mod;
}
bool ok(int l1,int r1,int l2,int r2){
	return (r1<l2)&&q(l1,r1)==q(l2,r2);
}
signed main(){
	quick
	srand(time(0));
	p=rand()%27+31;
	int n;
	cin>>n;
	px[0]=1;
	rep(i,1,n) px[i]=px[i-1]*p%Mod;
	cin>>s;
	int a,b,c;
	cin>>a>>b>>c;
	build(n);
	fill(dp[0][0],dp[N-1][N-1]+N,INF);
	int ans=INF;
	rep(t,1,n){
		dp[t][t][0]=a;
		dp[t][t][1]=a+b+c;
		rep(i,t+1,n){
			int mn=INF;
			rep(j,0,i-t+1){
				dp[t][i][j]=dp[t][i-1][j]+a;
				if(j&&ok(t,t+j-1,i-j+1,i)) dp[t][i][j]=min(dp[t][i][j],dp[t][i-j][j]+c);
				if(j==i-t+1) dp[t][i][j]=min(dp[t][i][j],mn+b+c);
				mn=min(mn,dp[t][i][j]);
			}
		}
		int ret=INF;
		rep(j,0,n-t+1){
			ret=min(ret,dp[t][n][j]);
		}
		ans=min(ans,a*(t-1)+ret);
	}
	cout<<ans<<"\n";
	/*rep(i,3,n){
		rep(j,0,i-2){
			cout<<dp[3][i][j]<<" \n"[j==i-2];
		}
	}*/
	return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 69716 KB Output is correct
2 Correct 26 ms 69640 KB Output is correct
3 Correct 26 ms 69616 KB Output is correct
4 Correct 26 ms 69632 KB Output is correct
5 Correct 32 ms 69740 KB Output is correct
6 Correct 25 ms 69700 KB Output is correct
7 Correct 26 ms 69708 KB Output is correct
8 Correct 26 ms 69700 KB Output is correct
9 Correct 26 ms 69700 KB Output is correct
10 Correct 27 ms 69708 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 69700 KB Output is correct
2 Correct 28 ms 69716 KB Output is correct
3 Runtime error 1370 ms 141208 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 27 ms 69716 KB Output is correct
2 Correct 26 ms 69640 KB Output is correct
3 Correct 26 ms 69616 KB Output is correct
4 Correct 26 ms 69632 KB Output is correct
5 Correct 32 ms 69740 KB Output is correct
6 Correct 25 ms 69700 KB Output is correct
7 Correct 26 ms 69708 KB Output is correct
8 Correct 26 ms 69700 KB Output is correct
9 Correct 26 ms 69700 KB Output is correct
10 Correct 27 ms 69708 KB Output is correct
11 Correct 25 ms 69700 KB Output is correct
12 Correct 26 ms 69668 KB Output is correct
13 Incorrect 26 ms 69736 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 69716 KB Output is correct
2 Correct 26 ms 69640 KB Output is correct
3 Correct 26 ms 69616 KB Output is correct
4 Correct 26 ms 69632 KB Output is correct
5 Correct 32 ms 69740 KB Output is correct
6 Correct 25 ms 69700 KB Output is correct
7 Correct 26 ms 69708 KB Output is correct
8 Correct 26 ms 69700 KB Output is correct
9 Correct 26 ms 69700 KB Output is correct
10 Correct 27 ms 69708 KB Output is correct
11 Correct 25 ms 69700 KB Output is correct
12 Correct 26 ms 69668 KB Output is correct
13 Incorrect 26 ms 69736 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 69716 KB Output is correct
2 Correct 26 ms 69640 KB Output is correct
3 Correct 26 ms 69616 KB Output is correct
4 Correct 26 ms 69632 KB Output is correct
5 Correct 32 ms 69740 KB Output is correct
6 Correct 25 ms 69700 KB Output is correct
7 Correct 26 ms 69708 KB Output is correct
8 Correct 26 ms 69700 KB Output is correct
9 Correct 26 ms 69700 KB Output is correct
10 Correct 27 ms 69708 KB Output is correct
11 Correct 25 ms 69700 KB Output is correct
12 Correct 26 ms 69668 KB Output is correct
13 Incorrect 26 ms 69736 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 69716 KB Output is correct
2 Correct 26 ms 69640 KB Output is correct
3 Correct 26 ms 69616 KB Output is correct
4 Correct 26 ms 69632 KB Output is correct
5 Correct 32 ms 69740 KB Output is correct
6 Correct 25 ms 69700 KB Output is correct
7 Correct 26 ms 69708 KB Output is correct
8 Correct 26 ms 69700 KB Output is correct
9 Correct 26 ms 69700 KB Output is correct
10 Correct 27 ms 69708 KB Output is correct
11 Correct 27 ms 69700 KB Output is correct
12 Correct 28 ms 69716 KB Output is correct
13 Runtime error 1370 ms 141208 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -