제출 #854085

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
854085		denniskim	Copy and Paste 3 (JOI22_copypaste3)	C++17	0 / 100	3082 ms	37436 KiB

copypaste3

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

ll n;
char s[2510];
ll A, B, C;
ll dp[2510][2510];
ll je[2510];
ll nu[2510];
ll hs = 79;
ll ss = 1000000007;

ll sqrmtp(ll X, ll Y)
{
	ll ret = 1;
	
	while(Y)
	{
		if(Y & 1)
			ret = ret * X % ss;
		
		X = X * X % ss;
		Y >>= 1;
	}
	
	return ret;
}

ll f(ll L, ll R)
{
	ll ret = (nu[R] - nu[L - 1]) % ss * sqrmtp(je[L], ss - 2) % ss;
	return (ret % ss + ss) % ss;
}

ll comp(ll L1, ll R1, ll L2, ll R2)
{
	return f(L1, R1) == f(L2, R2);
}

int main(void)
{
	fastio
	
	cin >> n;
	
	for(ll i = 1 ; i <= n ; i++)
		cin >> s[i];
	
	cin >> A;
	cin >> B;
	cin >> C;
	
	je[0] = 1;
	
	for(ll i = 1 ; i <= n ; i++)
		je[i] = je[i - 1] * hs % ss;
	
	for(ll i = 1 ; i <= n ; i++)
		nu[i] = (nu[i - 1] + je[i] * (s[i] - 'a' + 1) % ss) % ss;
	
	for(ll i = 1 ; i <= n ; i++)
		dp[i][i] = A;
	
	for(ll L = 1 ; L < n ; L++)
	{
		for(ll i = 1 ; i <= n - L ; i++)
		{
			ll j = i + L;
			
			dp[i][j] = (L + 1) * A;
			dp[i][j] = min(dp[i][j], dp[i][j - 1] + A);
			
			for(ll k = 1 ; k < L ; k++)
			{
				ll sum = 0;
				ll p = i;
				
				while(1)
				{
					if(p > j - k)
						break;
					
					if(p + k - 1 <= j - k)
					{
						if(comp(p, p + k - 1, j - k + 1, j))
						{
							p += k;
							sum += C;
						}
						
						else
						{
							p++;
							sum += A;
						}
					}
					
					else
					{
						p++;
						sum += A;
					}
				}
				
				dp[i][j] = min(dp[i][j], dp[j - k + 1][j] + B + sum + C);
			}
		}
	}
	
	cout << dp[1][n];
	return 0;
}

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