Submission #544675

#	Time	Username	Problem	Language	Result	Execution time	Memory
544675		blue	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	592 ms	98764 KiB

copypaste3

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define sz(x) int(x.size())

const ll INF = 1'000'000'000'000'000'000LL;


const int mx = 2'500;

const ll mod = 1'000'000'000'000'007LL;


ll mul(ll a, ll b)
{
	return (a*b)%mod;
}

const int pr = 59;
ll P[1+mx];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	cin >> N;

	string S;
	cin >> S;
	S = " " + S;

	ll A, B, C;
	cin >> A >> B >> C;

	ll DP[1+N][1+N];
	for(int l = 1; l <= N; l++)
		for(int r = l; r <= N; r++)
			DP[l][r] = A * (r-l+1);

	P[0] = 1;
	P[1] = pr;
	for(int i = 2; i <= N; i++)
		P[i] = mul(P[i-1], pr);


	ll hsh[1+N][1+N];
	for(int l = 1; l <= N; l++)
	{
		hsh[l][l] = (S[l] - 'a' + 1);
		for(int r = l+1; r <= N; r++)
		{
			hsh[l][r] = (hsh[l][r-1] * P[1]  +  (S[r] - 'a' + 1)) % mod;
		}
	}

	// cerr << "done\n";


	for(int d = 0; d < N; d++)
	{
		// cerr << "\n\n\n\n";
		// cerr << "d = " << d << '\n';
		vi nxt(1+N, 0);
		for(int r = d; r <= N; r++)
			nxt[r] = r;

		vector<pll> values;
		for(int l = 1; l+d <= N; l++)
			values.push_back({hsh[l][l+d], l+d});

		// for(pll v : values) cerr << v.first << "/" << v.second << " ";
		// 	cerr << '\n';

		sort(values.begin(), values.end());

		// cerr << "?\n";

		while(!values.empty())
		{
			ll ch = values.back().first;

			// cerr << "ch = " << ch << '\n';
			// cerr << sz(values) << '\n';

			for(int li = sz(values)-1; li >= 0 && values[li].first == ch; li--)
			{
				// cerr << "li = " << li << '\n';
				while(sz(values)-1 > li && values[sz(values)-2].second >= values[li].second + d + 1)
					values.pop_back();

				if(values.back().second >= values[li].second + d + 1)
					nxt[ values[li].second ] = values.back().second;
				// cerr << "dn\n";
			}

			while(!values.empty() && values.back().first == ch)
				values.pop_back();
		}
		// cerr << "#\n";

		// cerr << "nxt = ";
		// for(int l = 1; l <= N; l++) cerr << nxt[l] << ' ';
		// 	cerr << '\n';

		if(d > 0)
		{
			for(int l = 1; l+d <= N; l++)
			{
				int r = l+d;
				DP[l][r] = min(DP[l][r], min(A + DP[l+1][r], DP[l][r-1] + A));
			}
		}


		for(int r = 1+d; r <= N; r++)
		{
			int l = r-d;
			int nr = r;
			for(int ct = 2; 1; ct++)
			{
				if(nxt[nr] == nr) break;
				nr = nxt[nr];

				// cerr << l << ' ' << r << " -> " << ct << " ? " << nr << '\n';

				// cerr << nr-l+1 - ct*(d+1) << " AAA \n";

				DP[l][nr] = min(DP[l][nr], DP[l][r] + B + C*ct + A*(nr-l+1 - ct*(d+1)));
			}

			// cerr << l << ' ' << r << " : " << DP[l][r] << '\n';
		}
	}

	cout << DP[1][N] << '\n';
}

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