Submission #544594

#	Time	Username	Problem	Language	Result	Execution time	Memory
544594		pavement	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	954 ms	34260 KiB

copypaste3

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

const int p = 31, p2 = 53, MOD = 1e9 + 9, MOD2 = 1e9 + 7;
int N, A, B, C, dp[2505][2505], phsh[2505], phsh2[2505], powp[2505], powp2[2505], invpowp[2505], invpowp2[2505], nxt[2505];
char S[2505];
map<ii, vector<int> > vec;

int exp_mod(int a, int b, int m) {
	int r = 1;
	while (b) {
		if (b & 1ll) r = r * a % m;
		a = a * a % m;
		b >>= 1ll;
	}
	return r;
}

ii hsh(int l, int r) {
	int tmp = (phsh[r] - phsh[l - 1]) * invpowp[l - 1] % MOD;
	int tmp2 = (phsh2[r] - phsh2[l - 1]) * invpowp2[l - 1] % MOD2;
	return mp((tmp + MOD) % MOD, (tmp2 + MOD2) % MOD2);
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		if (i == 0) powp[i] = powp2[i] = 1;
		else powp[i] = powp[i - 1] * p % MOD, powp2[i] = powp2[i - 1] * p2 % MOD2;
		invpowp[i] = exp_mod(powp[i], MOD - 2, MOD);
		invpowp2[i] = exp_mod(powp2[i], MOD2 - 2, MOD2);
	}
	for (int i = 1; i <= N; i++) {
		cin >> S[i];
		phsh[i] = (phsh[i - 1] + (S[i] - 'a' + 1) * powp[i - 1]) % MOD;
		phsh2[i] = (phsh2[i - 1] + (S[i] - 'a' + 1) * powp2[i - 1]) % MOD2;
	}
	cin >> A >> B >> C;
	for (int i = 1; i <= N; i++)
		for (int j = i; j <= N; j++) dp[i][j] = (j - i + 1) * A;
	for (int i = 1; i <= N; i++) {
		vec.clear();
		for (int j = 1; j + i - 1 <= N; j++)
			vec[hsh(j, j + i - 1)].pb(j);
		for (auto j : vec) {
			reverse(j.second.begin(), j.second.end());
			for (int k = 0, ptr = 0; k < j.second.size(); k++) {
				while (ptr + 1 < j.second.size() && j.second[ptr + 1] - j.second[k] >= i) ptr++;
				if (j.second[ptr] - j.second[k] >= i) nxt[j.second[k]] = j.second[ptr];
				else nxt[j.second[k]] = -1;
			}
		}
		for (int j = 1; j + i - 1 <= N; j++) {
			if (i > 1) dp[j][j + i - 1] = min({dp[j][j + i - 1], dp[j + 1][j + i - 1] + A, dp[j][j + i - 2] + A});
			for (int curr = j, k = 1; curr != -1; k++, curr = nxt[curr])
				dp[j][curr + i - 1] = min(dp[j][curr + i - 1], (curr + i - j) * A - k * i * A + dp[j][j + i - 1] + k * C + B);
		}
	}
	cout << dp[1][N] << '\n';
}

Compilation message (stderr)

copypaste3.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main() {
      | ^~~~
copypaste3.cpp: In function 'int main()':
copypaste3.cpp:74:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |    for (int k = 0, ptr = 0; k < j.second.size(); k++) {
      |                             ~~^~~~~~~~~~~~~~~~~
copypaste3.cpp:75:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     while (ptr + 1 < j.second.size() && j.second[ptr + 1] - j.second[k] >= i) ptr++;
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~

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