Submission #1305658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305658		vlomaczk	Copy and Paste 3 (JOI22_copypaste3)	C++20	6 / 100	570 ms	49560 KiB

copypaste3

#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<ll>> dp(n,vector<ll>(n, 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] = A;
			}
			if(j<n-1) dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 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] = min(dp[i][x+d], dp[i][j] + B + C*ile);
				} else break;
			}
			if(i>0) dp[i-1][j] = min(dp[i-1][j], dp[i][j] + A);
		}
	}	
	cout << dp[0][n-1] << "\n";

	return 0;
}

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