oj.uz

Submission #564976

# Submission time Handle Problem Language Result Execution time Memory
564976 2022-05-20T06:15:16 Z Zanite Copy and Paste 3 (JOI22_copypaste3) C++17
1 / 100
 688 ms 99532 KB 
#include <bits/stdc++.h>
using namespace std;

using ll	= long long;
using pll	= pair<ll, ll>;

#define fi	first
#define se	second

const ll mod	= 1707726299;
const ll maxN	= 2515;
const ll maxNr	= 2510;
const ll INF	= 1e18;

void maddto(ll &x, ll y) {x += y; x %= mod;}
ll msub(ll x, ll y) {x -= y; while (x < 0) x += mod; x %= mod; return x;}
ll mmul(ll x, ll y) {x *= y; x %= mod; return x;}

void chmin(ll &x, ll y) {x = min(x, y);}

ll modexp(ll x, ll y) {
	if (!x) return 0; if (!y) return 1;
	ll t = modexp(x, y >> 1);
	return mmul(t, mmul(t, (y & 1) ? x : 1));
}

ll A, B, C, N;
char S[maxN];

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<ll> uid(1e5, 2e5);
ll key = uid(rng), invkey = modexp(key, mod-2);
ll kpow[maxN], invkpow[maxN], hsh[maxN];

ll dp[maxN][maxN], nxt[maxN][maxN];

void precomp() {
	key = rng();
	invkey = modexp(key, mod-2);
	kpow[0] = invkpow[0] = 1;
	for (ll i = 1; i <= maxNr; i++) {
		kpow[i] = mmul(kpow[i-1], key);
		invkpow[i] = mmul(invkpow[i-1], invkey);
	}
}

void hashS() {
	for (ll i = 1; i <= N; i++) {
		hsh[i] = mmul(S[i], kpow[i]);
		maddto(hsh[i], hsh[i-1]);
	}
}

ll getHash(ll l, ll r) {
	ll ret = msub(hsh[r], hsh[l-1]);
	return mmul(ret, invkpow[l-1]);
}

int main() {
	precomp();

	scanf("%lld", &N);
	S[0] = '#';
	scanf("%s", S + 1);
	//N = strlen(S) - 1;
	scanf("%lld %lld %lld", &A, &B, &C);

	hashS();

	// compute nxt[l][r] for each possible substring length
	memset(nxt, -1, sizeof(nxt));
	for (ll len = 1; len < N; len++) {
		vector<pll> hashes = {{-1, -1}};
		for (ll st = 1; st <= N-len+1; st++) {
			hashes.push_back({getHash(st, st+len-1), st});
		}
		sort(hashes.begin(), hashes.end());
		/*
		for (auto H : hashes) {
			printf("{%lld, %lld} ", H.fi, H.se);
		}
		cout << '\n';
		*/

		deque<ll> pending;
		for (ll i = 1; i < hashes.size(); i++) {
			if (hashes[i].fi != hashes[i-1].fi) {
				pending.clear();
			}
			while (!pending.empty()) {
				if (pending.front() <= hashes[i].se - len) {
					nxt[pending.front()][pending.front()+len-1] = hashes[i].se;
					pending.pop_front();
				} else break;
			}
			pending.push_back(hashes[i].se);
		}
	}

	/*
	for (ll l = 1; l <= N; l++) {
		for (ll r = l; r <= N; r++) {
			printf("nxt[%lld][%lld] = %lld\n", l, r, nxt[l][r]);
		}
	}
	*/

	// Calculate DP
	for (auto &i : dp) {
		for (auto &j : i) {
			j = INF;
		}
	}
	// Base case
	for (ll i = 1; i < N; i++) {
		dp[i][i] = A + B;
	}
	// Transition
	for (ll len = 1; len < N; len++) {
		for (ll l = 1; l <= N-len+1; l++) {
			ll r = l+len-1;

			// Type S[l-1]
			if (l > 1) {
				chmin(dp[l-1][r], dp[l][r] + A);
			}

			// Type S[r+1]
			if (r < N) {
				chmin(dp[l][r+1], dp[l][r] + A);
			}

			// Paste next occurences of S[l..r]
			ll cur = l, pastes = 1;
			while (nxt[cur][cur+len-1] != -1) {
				cur = nxt[cur][cur+len-1];
				pastes++;
				chmin(
					dp[l][cur+len-1],
					dp[l][r] + 1ll * pastes * C + 1ll * (cur+len-l - 1ll * len * pastes) * A + B
				);
			}
		}
	}

	printf("%lld\n", dp[1][N] - B);
}

Compilation message

copypaste3.cpp: In function 'll modexp(ll, ll)':
copypaste3.cpp:22:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   22 |  if (!x) return 0; if (!y) return 1;
      |  ^~
copypaste3.cpp:22:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   22 |  if (!x) return 0; if (!y) return 1;
      |                    ^~
copypaste3.cpp: In function 'int main()':
copypaste3.cpp:86:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for (ll i = 1; i < hashes.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
copypaste3.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  scanf("%lld", &N);
      |  ~~~~~^~~~~~~~~~~~
copypaste3.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |  scanf("%s", S + 1);
      |  ~~~~~^~~~~~~~~~~~~
copypaste3.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |  scanf("%lld %lld %lld", &A, &B, &C);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 99276 KB Output is correct
2 Correct 41 ms 99344 KB Output is correct
3 Correct 44 ms 99356 KB Output is correct
4 Correct 41 ms 99256 KB Output is correct
5 Correct 44 ms 99304 KB Output is correct
6 Correct 41 ms 99276 KB Output is correct
7 Correct 39 ms 99256 KB Output is correct
8 Correct 40 ms 99344 KB Output is correct
9 Correct 40 ms 99312 KB Output is correct
10 Correct 46 ms 99276 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 99300 KB Output is correct
2 Correct 40 ms 99264 KB Output is correct
3 Correct 330 ms 99340 KB Output is correct
4 Correct 425 ms 99460 KB Output is correct
5 Correct 466 ms 99532 KB Output is correct
6 Correct 568 ms 99480 KB Output is correct
7 Correct 688 ms 99488 KB Output is correct
8 Correct 685 ms 99516 KB Output is correct
9 Correct 682 ms 99404 KB Output is correct
10 Incorrect 41 ms 99296 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 99276 KB Output is correct
2 Correct 41 ms 99344 KB Output is correct
3 Correct 44 ms 99356 KB Output is correct
4 Correct 41 ms 99256 KB Output is correct
5 Correct 44 ms 99304 KB Output is correct
6 Correct 41 ms 99276 KB Output is correct
7 Correct 39 ms 99256 KB Output is correct
8 Correct 40 ms 99344 KB Output is correct
9 Correct 40 ms 99312 KB Output is correct
10 Correct 46 ms 99276 KB Output is correct
11 Correct 50 ms 99328 KB Output is correct
12 Correct 39 ms 99236 KB Output is correct
13 Correct 41 ms 99336 KB Output is correct
14 Correct 39 ms 99356 KB Output is correct
15 Correct 40 ms 99320 KB Output is correct
16 Correct 43 ms 99288 KB Output is correct
17 Correct 40 ms 99352 KB Output is correct
18 Incorrect 40 ms 99276 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 99276 KB Output is correct
2 Correct 41 ms 99344 KB Output is correct
3 Correct 44 ms 99356 KB Output is correct
4 Correct 41 ms 99256 KB Output is correct
5 Correct 44 ms 99304 KB Output is correct
6 Correct 41 ms 99276 KB Output is correct
7 Correct 39 ms 99256 KB Output is correct
8 Correct 40 ms 99344 KB Output is correct
9 Correct 40 ms 99312 KB Output is correct
10 Correct 46 ms 99276 KB Output is correct
11 Correct 50 ms 99328 KB Output is correct
12 Correct 39 ms 99236 KB Output is correct
13 Correct 41 ms 99336 KB Output is correct
14 Correct 39 ms 99356 KB Output is correct
15 Correct 40 ms 99320 KB Output is correct
16 Correct 43 ms 99288 KB Output is correct
17 Correct 40 ms 99352 KB Output is correct
18 Incorrect 40 ms 99276 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 99276 KB Output is correct
2 Correct 41 ms 99344 KB Output is correct
3 Correct 44 ms 99356 KB Output is correct
4 Correct 41 ms 99256 KB Output is correct
5 Correct 44 ms 99304 KB Output is correct
6 Correct 41 ms 99276 KB Output is correct
7 Correct 39 ms 99256 KB Output is correct
8 Correct 40 ms 99344 KB Output is correct
9 Correct 40 ms 99312 KB Output is correct
10 Correct 46 ms 99276 KB Output is correct
11 Correct 50 ms 99328 KB Output is correct
12 Correct 39 ms 99236 KB Output is correct
13 Correct 41 ms 99336 KB Output is correct
14 Correct 39 ms 99356 KB Output is correct
15 Correct 40 ms 99320 KB Output is correct
16 Correct 43 ms 99288 KB Output is correct
17 Correct 40 ms 99352 KB Output is correct
18 Incorrect 40 ms 99276 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 99276 KB Output is correct
2 Correct 41 ms 99344 KB Output is correct
3 Correct 44 ms 99356 KB Output is correct
4 Correct 41 ms 99256 KB Output is correct
5 Correct 44 ms 99304 KB Output is correct
6 Correct 41 ms 99276 KB Output is correct
7 Correct 39 ms 99256 KB Output is correct
8 Correct 40 ms 99344 KB Output is correct
9 Correct 40 ms 99312 KB Output is correct
10 Correct 46 ms 99276 KB Output is correct
11 Correct 41 ms 99300 KB Output is correct
12 Correct 40 ms 99264 KB Output is correct
13 Correct 330 ms 99340 KB Output is correct
14 Correct 425 ms 99460 KB Output is correct
15 Correct 466 ms 99532 KB Output is correct
16 Correct 568 ms 99480 KB Output is correct
17 Correct 688 ms 99488 KB Output is correct
18 Correct 685 ms 99516 KB Output is correct
19 Correct 682 ms 99404 KB Output is correct
20 Incorrect 41 ms 99296 KB Output isn't correct
21 Halted 0 ms 0 KB -