Submission #567421

#	Time	Username	Problem	Language	Result	Execution time	Memory
567421		8e7	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	810 ms	123056 KiB

copypaste3

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 2505
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1LL<<60;
int nxt[maxn][maxn];

ll dp[maxn][maxn], g[maxn][maxn];
int main() {
	io
	int n;
	cin >> n;
	string s;
	cin >> s;
	ll A, B, C;
	cin >> A >> B >> C;

	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			dp[i][j] = inf, nxt[i][j] = 1<<30;
			g[i][j] = inf;
		}
	}
	for (int i = 0;i < n;i++) {
		string t = s.substr(i, n - i);
		int siz = n - i;
		vector<int> z(siz, 0), fi(siz, 1<<30);
		int lef = 0, rig = 0;
		for (int j = 1;j < siz;j++) {
			if (j > rig) lef = j, rig = j;	
			else z[j] = min(z[j - lef], rig - j + 1);	
			while (j + z[j] < siz && t[j + z[j]] == t[z[j]]) z[j]++; 		
			int v = min(j, z[j]);
			fi[v] = min(fi[v], j);	

			if (j + z[j] - 1 > rig) lef = j, rig = j + z[j] - 1;
		}
		for (int j = siz - 2;j >= 0;j--) fi[j] = min(fi[j], fi[j+1]);	
		for (int j = 1;j < siz;j++) {
			nxt[i][j-1] = i + fi[j];
			if (nxt[i][j-1] < n) debug(i, j-1, i + fi[j]);
		}
	}
	for (int x = 0;x < n;x++) {
		for (int i = 0;i < n - x;i++) {
			int j = i + x;
			dp[i][j] = min(dp[i][j], A * (x + 1) + B);
			g[i][j] = min(g[i][j], dp[i][j] + C + B);
			if (i) {
				dp[i-1][j] = min(dp[i-1][j], g[i][j] + A);
				g[i-1][j] = min(g[i-1][j], g[i][j] + A);
			}
			if (j < n - 1) dp[i][j+1] = min(dp[i][j+1], dp[i][j] + A);
			int cur = nxt[i][x], cnt = 2;
			//debug(i, j);
			while (cur < n) {
				//debug("to", cur, cur + x, dp[i][j] + C * (cnt) + (cur + x - i + 1 - ((x+1) * cnt)) * A + B);
				dp[i][cur + x] = min(dp[i][cur + x], dp[i][j] + C * (cnt) + (cur + x - i + 1 - ((x+1) * cnt)) * A + B);
				g[i][cur + x] = min(g[i][cur + x], dp[i][cur + x]); 
				cur = nxt[cur][x];
				cnt++;
			}
			//debug(i, j, dp[i][j]);
		}
		//debug();
	}	
	cout << dp[0][n-1] - B << endl;
}

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
copypaste3.cpp:57:25: note: in expansion of macro 'debug'
   57 |    if (nxt[i][j-1] < n) debug(i, j-1, i + fi[j]);
      |                         ^~~~~

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