제출 #565337

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
565337		Zanite	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	832 ms	99692 KiB

copypaste3

#include <bits/stdc++.h>
using namespace std;

using ll	= long long;
using i8	= __int128;
using pll	= pair<ll, ll>;
using pi8	= pair<i8, i8>;

#define fi	first
#define se	second

const i8 mod	= 1850294015875828717;

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

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

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

i8 modexp(i8 x, i8 y) {
	if (!x) return 0; if (!y) return 1;
	i8 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);
i8 key = uid(rng), invkey = modexp(key, mod-2);
i8 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]);
	}
}

i8 getHash(ll l, ll r) {
	i8 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);
	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<pi8> 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);
}

컴파일 시 표준 에러 (stderr) 메시지

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

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