제출 #1317701

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317701		gelastropod	Copy and Paste 3 (JOI22_copypaste3)	C++20	0 / 100	1 ms	404 KiB

copypaste3

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
	int N, A, B, C, cnt = 1; cin >> N;
	string S; cin >> S >> A >> B >> C;
	vector<int> s = { 26 };
	for (char i : S) s.push_back(i - 'a');
	vector<vector<int>> vals(1, vector<int>(27, -1)), idxs(1, vector<int>()), children(1, vector<int>()), f(N, vector<int>(N, 0)), p(N, vector<int>(N, -1)), dp(N, vector<int>(N, INT_MAX));
	vector<vector<pair<int, int>>> toupd(N, vector<pair<int, int>>());
	for (int i = 0; i < N; i++) {
		int crnt = 0;
		for (int j = i; j >= -1; j--) {
			if (vals[crnt][s[j + 1]] == -1) {
				vals[crnt][s[j + 1]] = cnt++;
				vals.push_back(vector<int>(27, -1));
				idxs.push_back(vector<int>());
				children.push_back(vector<int>());
				children[crnt].push_back(s[j + 1]);
			}
			for (int k : children[crnt])
				if (k != s[j + 1])
					for (int l : idxs[vals[crnt][k]])
						f[i][l] = f[l][i] = i - j;
			crnt = vals[crnt][s[j + 1]];
			idxs[crnt].push_back(i);
		}
	}
	for (int i = 1; i < N; i++) {
		int lb = 0;
		for (int j = i - 1; j >= 0; j--)
			while (lb <= i - j - 1 && lb < f[i][j])
				p[i][lb++] = j;
	}
	for (int i = 0; i < N; i++) {
		dp[i][i] = A;
		for (int j = 0; j < N; j++) if (p[i][j] != -1) toupd[p[i][j]].push_back({ j, 2 });
		int crnt = INT_MAX;
		for (int j = i - 1; j >= 0; j--) {
			dp[i][j] = dp[i - 1][j] + A;
			for (auto k : toupd[j]) {
				if (k.second > 0) {
					if (p[j][k.first] != -1)
						toupd[p[j][k.first]].push_back({ k.first, k.second + 1 });
					toupd[j - k.first - 1].push_back({ k.first, -k.second });
				}
				else
					crnt = min(crnt, -(C - (k.first + 1) * A) * k.second + dp[i][i - k.first]);
				
			}
			toupd[j].clear();
			dp[i][j] = min(dp[i][j], (i - j + 1) * A + B + crnt);
		}
	}
	cout << dp[N - 1][0] << '\n';
}

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