oj.uz

답안 #713954

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
713954 2023-03-23T10:14:17 Z 089487 Copy and Paste 3 (JOI22_copypaste3) C++14
1 / 100
 1486 ms 141164 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)&&(l1<=r1)&&(l2<=r2)&&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+1){
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 69660 KB Output is correct
2 Correct 27 ms 69716 KB Output is correct
3 Correct 29 ms 69616 KB Output is correct
4 Correct 28 ms 69656 KB Output is correct
5 Correct 32 ms 69736 KB Output is correct
6 Correct 28 ms 69604 KB Output is correct
7 Correct 30 ms 69708 KB Output is correct
8 Correct 28 ms 69664 KB Output is correct
9 Correct 27 ms 69844 KB Output is correct
10 Correct 29 ms 69712 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 69752 KB Output is correct
2 Correct 26 ms 69716 KB Output is correct
3 Runtime error 1486 ms 141164 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 69660 KB Output is correct
2 Correct 27 ms 69716 KB Output is correct
3 Correct 29 ms 69616 KB Output is correct
4 Correct 28 ms 69656 KB Output is correct
5 Correct 32 ms 69736 KB Output is correct
6 Correct 28 ms 69604 KB Output is correct
7 Correct 30 ms 69708 KB Output is correct
8 Correct 28 ms 69664 KB Output is correct
9 Correct 27 ms 69844 KB Output is correct
10 Correct 29 ms 69712 KB Output is correct
11 Correct 27 ms 69716 KB Output is correct
12 Correct 31 ms 69708 KB Output is correct
13 Incorrect 26 ms 69688 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 69660 KB Output is correct
2 Correct 27 ms 69716 KB Output is correct
3 Correct 29 ms 69616 KB Output is correct
4 Correct 28 ms 69656 KB Output is correct
5 Correct 32 ms 69736 KB Output is correct
6 Correct 28 ms 69604 KB Output is correct
7 Correct 30 ms 69708 KB Output is correct
8 Correct 28 ms 69664 KB Output is correct
9 Correct 27 ms 69844 KB Output is correct
10 Correct 29 ms 69712 KB Output is correct
11 Correct 27 ms 69716 KB Output is correct
12 Correct 31 ms 69708 KB Output is correct
13 Incorrect 26 ms 69688 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 69660 KB Output is correct
2 Correct 27 ms 69716 KB Output is correct
3 Correct 29 ms 69616 KB Output is correct
4 Correct 28 ms 69656 KB Output is correct
5 Correct 32 ms 69736 KB Output is correct
6 Correct 28 ms 69604 KB Output is correct
7 Correct 30 ms 69708 KB Output is correct
8 Correct 28 ms 69664 KB Output is correct
9 Correct 27 ms 69844 KB Output is correct
10 Correct 29 ms 69712 KB Output is correct
11 Correct 27 ms 69716 KB Output is correct
12 Correct 31 ms 69708 KB Output is correct
13 Incorrect 26 ms 69688 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 69660 KB Output is correct
2 Correct 27 ms 69716 KB Output is correct
3 Correct 29 ms 69616 KB Output is correct
4 Correct 28 ms 69656 KB Output is correct
5 Correct 32 ms 69736 KB Output is correct
6 Correct 28 ms 69604 KB Output is correct
7 Correct 30 ms 69708 KB Output is correct
8 Correct 28 ms 69664 KB Output is correct
9 Correct 27 ms 69844 KB Output is correct
10 Correct 29 ms 69712 KB Output is correct
11 Correct 27 ms 69752 KB Output is correct
12 Correct 26 ms 69716 KB Output is correct
13 Runtime error 1486 ms 141164 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -