Submission #1208988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208988		aaron_dcoder	Copy and Paste 3 (JOI22_copypaste3)	C++20	100 / 100	2065 ms	49640 KiB

copypaste3

#define NDEBUG

#ifdef NDEBUG
#define dbg(TXTMSG) if constexpr (false) cerr << "lol"
#define dbgv(VARN) ((void)0)
#define dbgfor(COND) if constexpr (false) for (COND)

#else
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#pragma GCC optimize("trapv")
#define dbg(TXTMSG) cerr << "\n" << TXTMSG
#define dbgv(VARN) cerr << "\n" << #VARN << " = "<< VARN << ", line " << __LINE__ << "\n"
#define dbgfor(COND) for (COND)

#endif

#include <bits/stdc++.h>

using namespace std;
using ll = long long; 
using pll = pair<ll,ll>;
#define e0 first
#define e1 second
constexpr ll INFTY = 2e18;

constexpr __int128 mod = (__int128(1)<<61) - __int128(1);
__int128 powmod(__int128 b, ll e)
{
	__int128 o = 1;
	while (e>0)
	{
		if (e%2==1)
		{
			o*=b;
			o%=mod;
		}
		b*=b;
		b%=mod;
		e/=2;
	}
	return o;
}
int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	dbgv("Started");

	ll N,A,B,C;
	string S;
	cin >> N >> S >> A >> B >> C;

	__int128 base = (time(0))%mod;
	vector<__int128> hashsum(N+1);
	hashsum[0] = S[0]-'a'+1;
	for (ll i = 0; i < N; ++i)
	{
		hashsum[i+1]=hashsum[i] + (__int128(S[i]-'a'+1))*powmod(base,i);
		hashsum[i+1]%=mod;
	}

	auto gethash = [&](ll l, ll r)
	{
		return (((hashsum[r+1]-hashsum[l]+mod)%mod)*powmod(base,mod-1-l))%mod;
	};


	dbgv("hasdone");

	vector<vector<ll>> nextcpy(N+1,vector<ll>());
	for (ll l = 0; l <= N; ++l)
	{
		nextcpy[l].assign(N-l+1, INFTY);
		map<__int128,ll> seenhashidx;
		for (ll i = N-2*l; i >= 0; --i)
		{
			seenhashidx[gethash(i+l,i+2*l-1)] = i+l;

			auto it = seenhashidx.find(gethash(i,i+l-1));
			if (it==seenhashidx.end())
			{
				nextcpy[l][i] = INFTY;
			}
			else
			{
				nextcpy[l][i] = it->e1;
			}
		}
	}
	//dbgv("ncpy done");
	for (ll i = 0; i < N; ++i)
	{
		dbgv(gethash(i,i));
		dbgv(nextcpy[1][i]);
	}


	vector<vector<ll>> cost(N+1, vector<ll>());
	for (ll l = 1; l <= N; ++l)
	{
		cost[l].assign(N-l+1, INFTY);
	}
	cost[0].assign(N+1,0);
	
	for (ll l = 1; l <= N; ++l)
	{
		for (ll i = 0; i <= N-l; ++i)
		{
			cost[l][i] = min({cost[l][i], cost[l-1][i]+A, A+cost[l-1][i+1]});

			ll eidx = nextcpy[l][i];
			dbgv(eidx);

			ll npaste = 2;
			while (eidx<INFTY)
			{
				cost[eidx-i+l][i] = min(cost[eidx-i+l][i], cost[l][i] + B + C*npaste + A*(eidx-i+l - l*npaste));
				npaste++;
				eidx = nextcpy[l][eidx];
			}
		}
	}

	for (ll i = 0; i < N-1; ++i)
	{
		//dbgv(gethash(i,i));
		dbgv(cost[2][i]);
	}

	cout << cost[N][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