oj.uz

답안 #564974

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
564974 2022-05-20T06:11:01 Z Zanite Copy and Paste 3 (JOI22_copypaste3) C++17
1 / 100
 700 ms 98892 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	= 2505;
const ll maxNr	= 2500;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 98464 KB Output is correct
2 Correct 40 ms 98452 KB Output is correct
3 Correct 39 ms 98508 KB Output is correct
4 Correct 39 ms 98580 KB Output is correct
5 Correct 39 ms 98508 KB Output is correct
6 Correct 38 ms 98576 KB Output is correct
7 Correct 37 ms 98496 KB Output is correct
8 Correct 40 ms 98472 KB Output is correct
9 Correct 42 ms 98572 KB Output is correct
10 Correct 41 ms 98476 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 98632 KB Output is correct
2 Correct 39 ms 98456 KB Output is correct
3 Correct 334 ms 98560 KB Output is correct
4 Correct 401 ms 98764 KB Output is correct
5 Correct 502 ms 98608 KB Output is correct
6 Correct 577 ms 98700 KB Output is correct
7 Correct 691 ms 98892 KB Output is correct
8 Correct 694 ms 98624 KB Output is correct
9 Correct 700 ms 98704 KB Output is correct
10 Incorrect 38 ms 98520 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 98464 KB Output is correct
2 Correct 40 ms 98452 KB Output is correct
3 Correct 39 ms 98508 KB Output is correct
4 Correct 39 ms 98580 KB Output is correct
5 Correct 39 ms 98508 KB Output is correct
6 Correct 38 ms 98576 KB Output is correct
7 Correct 37 ms 98496 KB Output is correct
8 Correct 40 ms 98472 KB Output is correct
9 Correct 42 ms 98572 KB Output is correct
10 Correct 41 ms 98476 KB Output is correct
11 Correct 39 ms 98500 KB Output is correct
12 Correct 39 ms 98672 KB Output is correct
13 Correct 38 ms 98508 KB Output is correct
14 Correct 40 ms 98572 KB Output is correct
15 Correct 38 ms 98464 KB Output is correct
16 Correct 38 ms 98492 KB Output is correct
17 Correct 41 ms 98504 KB Output is correct
18 Incorrect 44 ms 98468 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 98464 KB Output is correct
2 Correct 40 ms 98452 KB Output is correct
3 Correct 39 ms 98508 KB Output is correct
4 Correct 39 ms 98580 KB Output is correct
5 Correct 39 ms 98508 KB Output is correct
6 Correct 38 ms 98576 KB Output is correct
7 Correct 37 ms 98496 KB Output is correct
8 Correct 40 ms 98472 KB Output is correct
9 Correct 42 ms 98572 KB Output is correct
10 Correct 41 ms 98476 KB Output is correct
11 Correct 39 ms 98500 KB Output is correct
12 Correct 39 ms 98672 KB Output is correct
13 Correct 38 ms 98508 KB Output is correct
14 Correct 40 ms 98572 KB Output is correct
15 Correct 38 ms 98464 KB Output is correct
16 Correct 38 ms 98492 KB Output is correct
17 Correct 41 ms 98504 KB Output is correct
18 Incorrect 44 ms 98468 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 98464 KB Output is correct
2 Correct 40 ms 98452 KB Output is correct
3 Correct 39 ms 98508 KB Output is correct
4 Correct 39 ms 98580 KB Output is correct
5 Correct 39 ms 98508 KB Output is correct
6 Correct 38 ms 98576 KB Output is correct
7 Correct 37 ms 98496 KB Output is correct
8 Correct 40 ms 98472 KB Output is correct
9 Correct 42 ms 98572 KB Output is correct
10 Correct 41 ms 98476 KB Output is correct
11 Correct 39 ms 98500 KB Output is correct
12 Correct 39 ms 98672 KB Output is correct
13 Correct 38 ms 98508 KB Output is correct
14 Correct 40 ms 98572 KB Output is correct
15 Correct 38 ms 98464 KB Output is correct
16 Correct 38 ms 98492 KB Output is correct
17 Correct 41 ms 98504 KB Output is correct
18 Incorrect 44 ms 98468 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 98464 KB Output is correct
2 Correct 40 ms 98452 KB Output is correct
3 Correct 39 ms 98508 KB Output is correct
4 Correct 39 ms 98580 KB Output is correct
5 Correct 39 ms 98508 KB Output is correct
6 Correct 38 ms 98576 KB Output is correct
7 Correct 37 ms 98496 KB Output is correct
8 Correct 40 ms 98472 KB Output is correct
9 Correct 42 ms 98572 KB Output is correct
10 Correct 41 ms 98476 KB Output is correct
11 Correct 40 ms 98632 KB Output is correct
12 Correct 39 ms 98456 KB Output is correct
13 Correct 334 ms 98560 KB Output is correct
14 Correct 401 ms 98764 KB Output is correct
15 Correct 502 ms 98608 KB Output is correct
16 Correct 577 ms 98700 KB Output is correct
17 Correct 691 ms 98892 KB Output is correct
18 Correct 694 ms 98624 KB Output is correct
19 Correct 700 ms 98704 KB Output is correct
20 Incorrect 38 ms 98520 KB Output isn't correct
21 Halted 0 ms 0 KB -