Submission #761060

#	Time	Username	Problem	Language	Result	Execution time	Memory
761060		ymm	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	2154 ms	587444 KiB

copypaste3

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 2550;

int pre[N][N];
vector<pii> wright[N][N];
ll dp[N][N];
ll A, B, C;
char s[N];
int n;

// TODO: use kmp, this is O(n^3)
void make_pre()
{
	memset(pre, -1, sizeof(pre));
	Loop (r2,1,n+1) {
		int len = 1;
		LoopR (r1,len,r2) {
			if (r2-r1 < len)
				continue;
			if (memcmp(&s[r2-len], &s[r1-len], len) == 0) {
				pre[r2-len][r2] = r1-len;
				++len;
				++r1;
			}
		}
	}
}

void make_wright()
{
	//auto t1 = clock();
	Loop (l,0,n) Loop (r,l+1,n+1)
		wright[l][r].reserve(8);
	Loop (l,0,n) Loop (r,l+1,n+1) {
		int k = 1;
		int p = l;
		do {
			wright[p][r].push_back({r-l, k});
			p = pre[p][p+r-l];
			++k;
		} while (p != -1);
	}
	//auto t2 = clock();
	//cout << (double)(t2-t1)/CLOCKS_PER_SEC << '\n';
}

void calc_dp()
{
	Loop (r,1,n+1) LoopR (l,0,r) {
		dp[l][r] = min(dp[l][r-1], dp[l+1][r]) + A;
		for (auto [k, cnt] : wright[l][r])
			dp[l][r] = min(dp[l][r], dp[l][l+k] + B + C * cnt + A * (r-l - cnt*k));
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> s >> A >> B >> C;
	//n=2500;
	//memset(s, 'a', n);
	//A=B=C=1;
	make_pre();
	make_wright();
	calc_dp();
	cout << dp[0][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