Submission #936851

#	Time	Username	Problem	Language	Result	Execution time	Memory
936851		fyan	Copy and Paste 3 (JOI22_copypaste3)	C++14	30 / 100	1422 ms	98484 KiB

copypaste3

//source: https://oj.uz/problem/view/JOI22_copypaste3
#pragma GCC optimize("trapv")
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
using namespace std;
#define int long long
#define P pair
#define pi P<int,int>
#define f first
#define s second
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define V vector
#define vi V<int>
#define v2i V<vi>
#define v3i V<v2i>
#define vpi V<pi>
#define vb V<bool>
#define v2b V<vb>
#define pb push_back
#define S set
#define si S<int>
#define ins insert
#define era erase
#define M map
#define mii M<int,int>
#define Q queue
#define PQ priority_queue
const int MOD=1e9+7;
const int INF=1e18;
int smax(int& a, int b) {return a = max(a,b);}
int smin(int& a, int b) {return a = min(a,b);}

struct stringmatch {
	int n;
	int p = 29;
	int MOD = 1420696969;
	vector<int> pref, ppow;
	stringmatch() {}
	stringmatch(vector<int> arr) {
		n = arr.size();
		ppow.push_back(1);
		for (int i = 0; i < n+5; i++) {
			ppow.push_back((p * ppow[i])%MOD);
		}
		pref.push_back(0);
		for (int i = 0; i < n; i++) {
			pref.push_back((pref[i] + (arr[i]+1)*ppow[i])%MOD);
		}
	}
	bool equiv(int l1, int r1, int l2, int r2) {
		if (r1 - l1 != r2 - l2) return 0;
		if (l1 > l2) {
			swap(l1, l2);
			swap(r1, r2);
		}
		int sub1 = (pref[r1+1] - pref[l1] + MOD)%MOD;
		int sub2 = (pref[r2+1] - pref[l2] + MOD)%MOD;
		sub1 *= ppow[l2-l1]; sub1 %= MOD;
		return (sub1 == sub2);
	}
};

int n;
vi s;
int a, b, c;
v2i dp, nxt;
stringmatch sm;

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	cin >> n;
	for (int i = 0; i < n; i++) {
		char c; cin >> c; s.pb(c - 'a');
	}
	cin >> a >> b >> c;
	sm = stringmatch(s);
	nxt = v2i(n, vi(n, -1));
	for (int l = 0; l < n; l++) {
		for (int r = l; r < n; r++) {
			for (int sf = r-l+1; r + sf < n; sf++) {
				if (sm.equiv(l, r, l+sf, r+sf)) {
					nxt[l][r] = l + sf;
					break;
				}
			}
		}
	}
	dp = v2i(n, vi(n, INF));
	for (int i = 0; i < n; i++) {
		dp[i][i] = a;
	}
	for (int l = n-1; l >= 0; l--) {
		for (int r = l; r < n; r++) {
			//add letters
			if (r+1 < n) {
				smin(dp[l][r+1], dp[l][r]+a);
			}
			if (l > 0) {
				smin(dp[l-1][r], dp[l][r]+a);
			}
			//copy + paste
			int cost = dp[l][r] + b + c;
			int cl = l; int cr = r;
			while (nxt[cl][cr] != -1) {
				int nl = nxt[cl][cr];
				int nr = nl + r - l;
				cost += a * (nl - cr - 1);
				cost += c;
				smin(dp[l][nr], cost);
				cl = nl; cr = nr;
			}
		}
	}
	cout << dp[0][n-1];
	return 0;
}

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