제출 #634462

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
634462		LittleCube	Copy and Paste 3 (JOI22_copypaste3)	C++14	57 / 100	3074 ms	14156 KiB

copypaste3

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

const ll base = 29, mod = 1234567891;

int N;
char c[1005];
ll A, B, C, dp[1005][1005], h[1005][1005];

signed main()
{
	cin >> N;
	for(int i = 1; i <= N; i++)
		cin >> c[i];
	cin >> A >> B >> C;
	for(int i = 1; i <= N; i++)
		for(int j = i; j <= N; j++)
		{
			dp[i][j] = A * (j - i + 1);
			h[i][j] = (h[i][j - 1] * base + c[j] - 'a') % mod;
		}
	for(int i = N; i >= 1; i--)
		for(int k = i; k <= N; k++)
		{	
			for(int j = i + 1; j <= k; j++)
				dp[i][k] = min(dp[i][k], dp[j][k] + (j - i) * A);
			ll cur = dp[i][k] + B + C, pre = k;
			// cout << "copy: " << i << ' ' << k << " initial " << cur << '\n';
			for(int j = k + 1; j <= N; j++)
			{
				cur += A;
				if(pre < j - k + i && h[j - k + i][j] == h[i][k])
				{	
					cur += -(k - i + 1) * A + C;
					pre = j;
				}
				// cout << "copy: " << i << ' ' << k << " to " << i << ' ' << j << " cost " << cur << '\n';
				dp[i][j] = min(dp[i][j], cur);
			}
		}
	/* for(int i = 1; i <= N; i++)
		for(int j = 1; j <= N; j++)
			if(j < i) cout << "- ";
			else cout << dp[i][j] << " \n"[N == j];
	*/
	cout << dp[1][N] << '\n';
}

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