Submission #1305711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305711		vlomaczk	Copy and Paste 3 (JOI22_copypaste3)	C++20	100 / 100	1014 ms	245664 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 HashPair {
    size_t operator()(const pair<ll,ll>& p) const {
        return (uint64_t(p.first) << 32) ^ p.second;
    }
};

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));
	vector<pair<pair<ll, ll>, pair<ll, ll>>> H_mapa;
	for(int i=0; i<n; ++i) {
		for(int j=i; j<n; ++j) H_mapa.push_back({phash.get_hash(i,j),{i,j}});
	}
	sort(H_mapa.begin(), H_mapa.end());
	vector<vector<pair<ll, ll>>> next(n, vector<pair<ll, ll>>(n, {inf, inf}));
	vector<pair<ll, ll>> b; b.push_back(H_mapa[0].second);
	auto check_b = [&](vector<pair<ll, ll>> &b) {
		sort(b.begin(), b.end());
		int ile = b.size();
		int idx = ile;
		for(int i=ile-1; i>=0; --i) {
			auto[x,y] = b[i];
			while(idx > 0 && b[idx-1].first > b[i].second) idx--;
			if(idx < ile) next[b[i].first][b[i].second] = b[idx];
		}
	};
	for(int i=1; i<H_mapa.size(); ++i) {
		if(H_mapa[i].first==H_mapa[i-1].first) {
			b.push_back(H_mapa[i].second);
			continue;
		}
		check_b(b);
		while(b.size()) b.pop_back();
		b.push_back(H_mapa[i].second);
	}
	check_b(b);
	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, miedzy = 0;
			pair<ll, ll> x = {i,j};
			while(x.second < n) {
				dp[i][x.second] = min(dp[i][x.second], dp[i][j] + B + C*ile + A*miedzy);
				// if(i==2 && j==2) cout << dp[i][j] << " " << ile << " " << miedzy << " - " << x.first << " " << x.second << ", " << dp[i][j] + B + C*ile + A*miedzy << "\n";
				ile++;
				miedzy += next[x.first][x.second].first - x.second - 1;
				x = next[x.first][x.second];
			}

			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: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 32 / 32
• Subtask 6: 38 / 38