제출 #1144758

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144758		starchan	Copy and Paste 3 (JOI22_copypaste3)	C++20	57 / 100	3113 ms	1050116 KiB

copypaste3

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int MX = 3e3;
const int mod1 = 1e9+7;
const int mod2 = 1e9+9;

struct Mpair
{
	int v1, v2;
};

const Mpair b = {37, 31};
const Mpair ib = {621621626, 838709685};


Mpair make(int x)
{
	return {x, x};
}

Mpair operator+(const Mpair& M1, const Mpair& M2)
{
	Mpair ret = M1;
	ret.v1+=M2.v1; (ret.v1)%=mod1;
	ret.v2+=M2.v2; (ret.v2)%=mod2;
	return ret;
}

Mpair operator-(const Mpair& M1, const Mpair& M2)
{
	Mpair ret = M1;
	ret.v1-=M2.v1; ret.v1 += mod1; (ret.v1)%=mod1;
	ret.v2-=M2.v2; ret.v2 += mod2; (ret.v2)%=mod2;
	return ret;
}

Mpair operator*(const Mpair& M1, const Mpair& M2)
{
	Mpair ret = M1;
	ret.v1*=M2.v1; (ret.v1)%=mod1;
	ret.v2*=M2.v2; (ret.v2)%=mod2;
	return ret;
}

in convert(Mpair m)
{
	return {m.v1, m.v2};
}

Mpair ppow[MX];
Mpair ipow[MX];

void pre()
{
	ppow[0] = {1, 1};
	ipow[0] = {1, 1};
	for(int i = 1; i < MX; i++)
	{
		ppow[i] = ppow[i-1]*b;
		ipow[i] = ipow[i-1]*ib;
	}
	return;
}


signed main()
{
	fast(); pre();
	int n, a, b, c; cin >> n;
	vector<int> St(n+1, 0);
	vector<int> S(n+1, 0);
	for(int i = 1; i <= n; i++)
	{
		char xy; cin >> xy;
		St[i] = (xy - 'a' + 1);
		S[n+1-i] = St[i];
	}
	cin >> a >> b >> c;
	vector<Mpair> pref(n+1, {0,0});
	for(int i = 1; i <= n; i++)
		pref[i] = pref[i-1] + make(S[i])*ppow[i];
	
	map<in, vector<int>> lst;
	
	int forw[n+1][n+1];
	int g[n+1][n+1];
	
	for(int x = 1; x <= n; x++)
	{
		for(int i = 1; i <= n-x+1; i++)
		{
			in hsh = convert((pref[i+x-1]-pref[i-1])*ipow[i]);
			if(lst[hsh].empty())
				lst[hsh].pb(0);
			forw[n+2-(i+x)][x] = lst[hsh].back();
			lst[hsh].pb(i);
			vector<int> C = lst[hsh];
			if((i-1) < x)
			{
				g[(n+2)-(i+x)][x] = n+2-x;
				continue;
			}
			g[(n+2)-(i+x)][x] = (n+2)-(x+C[lower_bound(C.begin(), C.end(), i-x+1)-C.begin()-1]);
		}
		lst.clear();
	}

	vector<array<int, 3>> adj[n+1][n+1];
	for(int x = 1; x <= n; x++)
	{
		for(int i = 1; i <= n+1-x; i++)
		{
			int pl = i; pl = g[pl][x];
			int wt = 0;
			while(pl <= (n+1-x))
			{
				wt++;
				adj[i][pl+x-1].pb({i, i+x-1, (pl-i-wt*x)*a + (wt+1)*c + b});
				pl = g[pl][x];
			}
		}
	}

	int dp[n+1][n+1];

	for(int i = 1; i <= n; i++)
		dp[i][i] = a+b;

	for(int x = 2; x <= n; x++)
	{
		for(int i = 1; i <= (n+1-x); i++)
		{
			dp[i][i+x-1] = min(dp[i+1][i+x-1], dp[i][i+x-2]) + a;
			for(auto [l, r, w]: adj[i][i+x-1])
				dp[i][i+x-1] = min(dp[i][i+x-1], dp[l][r]+w);
		}
	}
	cout << (dp[1][n]-b) << "\n";
	return 0;
}	

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