Submission #1305657

#TimeUsernameProblemLanguageResultExecution timeMemory
1305657vlomaczkCopy and Paste 3 (JOI22_copypaste3)C++20
6 / 100
1624 ms343220 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

constexpr ll p = 31;
constexpr ll MAXN = 2510;
constexpr ll m1 = 1e9+7;
constexpr ll m2 = 1e9+9;
vector<pair<ll, ll>> powerP(MAXN, make_pair(1, 1));
pair<ll, ll> operator+(pair<ll, ll> a, pair<ll, ll> b) { return make_pair((a.first+b.first)%m1, (a.second+b.second)%m2); }
pair<ll, ll> operator-(pair<ll, ll> a, pair<ll, ll> b) { return make_pair((a.first-b.first+m1)%m1, (a.second-b.second+m2)%m2); }
pair<ll, ll> operator*(pair<ll, ll> a, pair<ll, ll> b) { return make_pair((a.first*b.first)%m1, (a.second*b.second)%m2); }
void update(pair<ll, ll> &p) {
    p.first%=m1; p.first+=m1; p.first%=m1;
    p.second%=m2; p.second+=m2; p.second%=m2;
}
bool operator==(pair<ll, ll> a, pair<ll, ll> b) {
    update(a); update(b);
    return (a.first==b.first && a.second==b.second);
}
pair<ll, ll> get_pair(ll x) {return make_pair(x, x);}
ll get_numer(char c) {return c-(int)'a' + 1;}

void genPow() {
	for(int i=1; i<MAXN; ++i) {
        powerP[i] = powerP[i-1]*get_pair(p);
    }
}

struct PolHash {
	string s;
	vector<pair<ll, ll>> H; // H is 1-indexed
	PolHash(string s_) { // s is 0-indexed
		s = s_;
		int n = s.size();
		H.assign(n+1, get_pair(0));
		for(int i=1; i<=n; ++i) {
			H[i] = get_pair(p)*H[i-1] + get_pair(get_numer(s[i-1]));
		}
	}

	pair<ll, ll> get_hash(int a, int b) { // 0-indexed
		++a; ++b;
		return H[b] - H[a-1]*powerP[b-a+1];
	}

	bool comp(int a, int b, int c, int d) {
		assert(a<=b); assert(c<=d);
		assert(b<s.size()); assert(d<s.size());
		if(get_hash(a,b)==get_hash(c,d)) return 1;
		return 0;
	}
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	genPow();

	int n; cin >> n;
	string s; cin >> s;
	ll A, B, C;
	cin >> A >> B >> C;
	ll inf = 1e18;
	PolHash phash(s);
	vector<vector<vector<ll>>> dp(n,vector<vector<ll>>(n, vector<ll>(2,inf)));
	for(ll d=0; d<n; ++d) {
		for(int i=0; i+d<n; ++i) {
			int j = i+d;
			if(i==j) {
				dp[i][j][0] = A;
				dp[i][j][1] = A + B;
			}
			dp[i][j][0] = min(dp[i][j][0], dp[i][j][1] + C);
			if(j<n-1) dp[i][j+1][0] = min(dp[i][j+1][0], dp[i][j][0] + A);
			ll ile = 1;
			for(int x=j+1; x+d<n; x+=d+1) {
				++ile;
				if(phash.comp(i,j,x,x+d)) {
					dp[i][x+d][0] = min(dp[i][x+d][0], dp[i][j][0] + B + C*ile);
					dp[i][x+d][1] = min(dp[i][x+d][1], dp[i][j][0] + B + C*ile - C);
				} else break;
			}

			dp[i][j][1] = min(dp[i][j][1], dp[i][j][0] + B);
			if(i>0) dp[i-1][j][1] = min(dp[i-1][j][1], dp[i][j][1] + A);

			dp[i][j][0] = min(dp[i][j][0], dp[i][j][1] + C);
		}
	}
	cout << dp[0][n-1][0] << "\n";

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...