Submission #733785

#	Time	Username	Problem	Language	Result	Execution time	Memory
733785		myrcella	Copy and Paste 3 (JOI22_copypaste3)	C++17	25 / 100	418 ms	174564 KiB

copypaste3

//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define ALL(x) x.begin(),x.end()
int lowbit(int x) {return x&(-x);}

const int maxn = 222;

int n;
ll A,B,C;
string s;
int a[maxn];
int len[maxn][maxn];
ll f[maxn][maxn][maxn],g[maxn][maxn];
pq <pair<pair<ll,int>,pii>,vector<pair<pair<ll,int>,pii>>,greater<pair<pair<ll,int>,pii>>> q;

int main() {
//	freopen("input.txt","r",stdin);	
	std::ios::sync_with_stdio(false);cin.tie(0);
	memset(f,inf,sizeof(f));
	cin>>n>>s>>A>>B>>C;
	rep(i,0,n) a[i] = (int)(s[i]-'a');
	rep(i,0,n)
		rep(j,i+1,n) {
			int x = i,y = j;
			while (y<n and a[x]==a[y]) x++,y++;
			len[i][j] = y-j; 
		}
	memset(f,inf,sizeof(f));
	memset(g,inf,sizeof(g));
	rep(i,0,n)
		rep(j,i,n) {
			g[i][j] = (j-i+1)*A + B;
			q.push({{g[i][j],-1},{i,j}});
		}
	while (!q.empty()) {
		if (q.top().fi.se==-1) { //g
			int i = q.top().se.fi, j = q.top().se.se;
			ll d = q.top().fi.fi;
			q.pop();
			if (g[i][j]!=d) continue;
			// update f
			if (f[i][j][j] > d + C) f[i][j][j] = d + C, q.push({{d+C,j},{i,j}});
			if (i-1>=0 and g[i-1][j] > d + A) g[i-1][j] = d + A, q.push({{d+A,-1},{i-1,j}});
		}
		else { //f
			int i = q.top().se.fi, j = q.top().se.se, k = q.top().fi.se;
			ll d = q.top().fi.fi;
			q.pop();
			if (f[i][j][k]!=d) continue;
			if (len[i][k+1] >= j-i+1 and f[i][j][k+j-i+1] > d + C) f[i][j][k+j-i+1] = d + C, q.push({{d+C,k+j-i+1},{i,j}});
			if (k+1<n and f[i][j][k+1] > d + A) f[i][j][k+1] = d + A, q.push({{d+A,k+1},{i,j}});
			if (g[i][k] > d + B) g[i][k] = d + B, q.push({{d+B,-1},{i,k}});
		}
	}
	ll ans = min(n*A,g[0][n-1] - B);
	rep(i,0,n) ans = min(ans,f[0][i][n-1]);
	cout<<ans;
	return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 0 / 5
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 0 / 32
• Subtask 6: 0 / 38