Submission #713952

#	Time	Username	Problem	Language	Result	Execution time	Memory
713952		089487	Copy and Paste 3 (JOI22_copypaste3)	C++14	1 / 100	1370 ms	141208 KiB

copypaste3

#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 / 1
• Subtask 2: 0 / 5
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 32
• Subtask 6: 0 / 38