oj.uz

Submission #761060

# Submission time Handle Problem Language Result Execution time Memory
761060 2023-06-19T07:09:47 Z ymm Copy and Paste 3 (JOI22_copypaste3) C++17
100 / 100
 2154 ms 587444 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 2550;

int pre[N][N];
vector<pii> wright[N][N];
ll dp[N][N];
ll A, B, C;
char s[N];
int n;

// TODO: use kmp, this is O(n^3)
void make_pre()
{
	memset(pre, -1, sizeof(pre));
	Loop (r2,1,n+1) {
		int len = 1;
		LoopR (r1,len,r2) {
			if (r2-r1 < len)
				continue;
			if (memcmp(&s[r2-len], &s[r1-len], len) == 0) {
				pre[r2-len][r2] = r1-len;
				++len;
				++r1;
			}
		}
	}
}

void make_wright()
{
	//auto t1 = clock();
	Loop (l,0,n) Loop (r,l+1,n+1)
		wright[l][r].reserve(8);
	Loop (l,0,n) Loop (r,l+1,n+1) {
		int k = 1;
		int p = l;
		do {
			wright[p][r].push_back({r-l, k});
			p = pre[p][p+r-l];
			++k;
		} while (p != -1);
	}
	//auto t2 = clock();
	//cout << (double)(t2-t1)/CLOCKS_PER_SEC << '\n';
}

void calc_dp()
{
	Loop (r,1,n+1) LoopR (l,0,r) {
		dp[l][r] = min(dp[l][r-1], dp[l+1][r]) + A;
		for (auto [k, cnt] : wright[l][r])
			dp[l][r] = min(dp[l][r], dp[l][l+k] + B + C * cnt + A * (r-l - cnt*k));
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> s >> A >> B >> C;
	//n=2500;
	//memset(s, 'a', n);
	//A=B=C=1;
	make_pre();
	make_wright();
	calc_dp();
	cout << dp[0][n] << '\n';
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 178388 KB Output is correct
2 Correct 79 ms 178416 KB Output is correct
3 Correct 79 ms 178388 KB Output is correct
4 Correct 81 ms 178496 KB Output is correct
5 Correct 78 ms 178380 KB Output is correct
6 Correct 80 ms 178376 KB Output is correct
7 Correct 99 ms 178436 KB Output is correct
8 Correct 82 ms 178420 KB Output is correct
9 Correct 80 ms 178380 KB Output is correct
10 Correct 80 ms 178380 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 178512 KB Output is correct
2 Correct 80 ms 178464 KB Output is correct
3 Correct 1074 ms 394212 KB Output is correct
4 Correct 1243 ms 431612 KB Output is correct
5 Correct 1556 ms 475672 KB Output is correct
6 Correct 1748 ms 526964 KB Output is correct
7 Correct 2154 ms 587400 KB Output is correct
8 Correct 2141 ms 587408 KB Output is correct
9 Correct 2127 ms 587444 KB Output is correct
10 Correct 80 ms 178456 KB Output is correct
11 Correct 80 ms 178440 KB Output is correct
12 Correct 85 ms 178436 KB Output is correct
13 Correct 81 ms 178444 KB Output is correct
14 Correct 81 ms 178492 KB Output is correct
15 Correct 82 ms 178440 KB Output is correct
16 Correct 83 ms 178516 KB Output is correct
17 Correct 93 ms 178420 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 178388 KB Output is correct
2 Correct 79 ms 178416 KB Output is correct
3 Correct 79 ms 178388 KB Output is correct
4 Correct 81 ms 178496 KB Output is correct
5 Correct 78 ms 178380 KB Output is correct
6 Correct 80 ms 178376 KB Output is correct
7 Correct 99 ms 178436 KB Output is correct
8 Correct 82 ms 178420 KB Output is correct
9 Correct 80 ms 178380 KB Output is correct
10 Correct 80 ms 178380 KB Output is correct
11 Correct 81 ms 178448 KB Output is correct
12 Correct 82 ms 178536 KB Output is correct
13 Correct 81 ms 178540 KB Output is correct
14 Correct 81 ms 178452 KB Output is correct
15 Correct 83 ms 178548 KB Output is correct
16 Correct 87 ms 178408 KB Output is correct
17 Correct 84 ms 178424 KB Output is correct
18 Correct 98 ms 178460 KB Output is correct
19 Correct 88 ms 178508 KB Output is correct
20 Correct 86 ms 178352 KB Output is correct
21 Correct 87 ms 178564 KB Output is correct
22 Correct 79 ms 178528 KB Output is correct
23 Correct 80 ms 178600 KB Output is correct
24 Correct 83 ms 178628 KB Output is correct
25 Correct 81 ms 178508 KB Output is correct
26 Correct 96 ms 178604 KB Output is correct
27 Correct 84 ms 178596 KB Output is correct
28 Correct 85 ms 178596 KB Output is correct
29 Correct 88 ms 178624 KB Output is correct
30 Correct 91 ms 178568 KB Output is correct
31 Correct 86 ms 178508 KB Output is correct
32 Correct 82 ms 178620 KB Output is correct
33 Correct 82 ms 178536 KB Output is correct
34 Correct 94 ms 178404 KB Output is correct
35 Correct 83 ms 178356 KB Output is correct
36 Correct 83 ms 178388 KB Output is correct
37 Correct 83 ms 178476 KB Output is correct
38 Correct 83 ms 178520 KB Output is correct
39 Correct 83 ms 178520 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 178388 KB Output is correct
2 Correct 79 ms 178416 KB Output is correct
3 Correct 79 ms 178388 KB Output is correct
4 Correct 81 ms 178496 KB Output is correct
5 Correct 78 ms 178380 KB Output is correct
6 Correct 80 ms 178376 KB Output is correct
7 Correct 99 ms 178436 KB Output is correct
8 Correct 82 ms 178420 KB Output is correct
9 Correct 80 ms 178380 KB Output is correct
10 Correct 80 ms 178380 KB Output is correct
11 Correct 81 ms 178448 KB Output is correct
12 Correct 82 ms 178536 KB Output is correct
13 Correct 81 ms 178540 KB Output is correct
14 Correct 81 ms 178452 KB Output is correct
15 Correct 83 ms 178548 KB Output is correct
16 Correct 87 ms 178408 KB Output is correct
17 Correct 84 ms 178424 KB Output is correct
18 Correct 98 ms 178460 KB Output is correct
19 Correct 88 ms 178508 KB Output is correct
20 Correct 86 ms 178352 KB Output is correct
21 Correct 87 ms 178564 KB Output is correct
22 Correct 79 ms 178528 KB Output is correct
23 Correct 80 ms 178600 KB Output is correct
24 Correct 83 ms 178628 KB Output is correct
25 Correct 81 ms 178508 KB Output is correct
26 Correct 96 ms 178604 KB Output is correct
27 Correct 84 ms 178596 KB Output is correct
28 Correct 85 ms 178596 KB Output is correct
29 Correct 88 ms 178624 KB Output is correct
30 Correct 91 ms 178568 KB Output is correct
31 Correct 86 ms 178508 KB Output is correct
32 Correct 82 ms 178620 KB Output is correct
33 Correct 82 ms 178536 KB Output is correct
34 Correct 94 ms 178404 KB Output is correct
35 Correct 83 ms 178356 KB Output is correct
36 Correct 83 ms 178388 KB Output is correct
37 Correct 83 ms 178476 KB Output is correct
38 Correct 83 ms 178520 KB Output is correct
39 Correct 83 ms 178520 KB Output is correct
40 Correct 86 ms 179032 KB Output is correct
41 Correct 93 ms 181296 KB Output is correct
42 Correct 93 ms 181004 KB Output is correct
43 Correct 84 ms 180928 KB Output is correct
44 Correct 86 ms 181020 KB Output is correct
45 Correct 86 ms 180968 KB Output is correct
46 Correct 89 ms 180896 KB Output is correct
47 Correct 88 ms 181104 KB Output is correct
48 Correct 86 ms 181020 KB Output is correct
49 Correct 88 ms 180912 KB Output is correct
50 Correct 89 ms 181016 KB Output is correct
51 Correct 89 ms 181004 KB Output is correct
52 Correct 87 ms 180956 KB Output is correct
53 Correct 84 ms 181024 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 178388 KB Output is correct
2 Correct 79 ms 178416 KB Output is correct
3 Correct 79 ms 178388 KB Output is correct
4 Correct 81 ms 178496 KB Output is correct
5 Correct 78 ms 178380 KB Output is correct
6 Correct 80 ms 178376 KB Output is correct
7 Correct 99 ms 178436 KB Output is correct
8 Correct 82 ms 178420 KB Output is correct
9 Correct 80 ms 178380 KB Output is correct
10 Correct 80 ms 178380 KB Output is correct
11 Correct 81 ms 178448 KB Output is correct
12 Correct 82 ms 178536 KB Output is correct
13 Correct 81 ms 178540 KB Output is correct
14 Correct 81 ms 178452 KB Output is correct
15 Correct 83 ms 178548 KB Output is correct
16 Correct 87 ms 178408 KB Output is correct
17 Correct 84 ms 178424 KB Output is correct
18 Correct 98 ms 178460 KB Output is correct
19 Correct 88 ms 178508 KB Output is correct
20 Correct 86 ms 178352 KB Output is correct
21 Correct 87 ms 178564 KB Output is correct
22 Correct 79 ms 178528 KB Output is correct
23 Correct 80 ms 178600 KB Output is correct
24 Correct 83 ms 178628 KB Output is correct
25 Correct 81 ms 178508 KB Output is correct
26 Correct 96 ms 178604 KB Output is correct
27 Correct 84 ms 178596 KB Output is correct
28 Correct 85 ms 178596 KB Output is correct
29 Correct 88 ms 178624 KB Output is correct
30 Correct 91 ms 178568 KB Output is correct
31 Correct 86 ms 178508 KB Output is correct
32 Correct 82 ms 178620 KB Output is correct
33 Correct 82 ms 178536 KB Output is correct
34 Correct 94 ms 178404 KB Output is correct
35 Correct 83 ms 178356 KB Output is correct
36 Correct 83 ms 178388 KB Output is correct
37 Correct 83 ms 178476 KB Output is correct
38 Correct 83 ms 178520 KB Output is correct
39 Correct 83 ms 178520 KB Output is correct
40 Correct 86 ms 179032 KB Output is correct
41 Correct 93 ms 181296 KB Output is correct
42 Correct 93 ms 181004 KB Output is correct
43 Correct 84 ms 180928 KB Output is correct
44 Correct 86 ms 181020 KB Output is correct
45 Correct 86 ms 180968 KB Output is correct
46 Correct 89 ms 180896 KB Output is correct
47 Correct 88 ms 181104 KB Output is correct
48 Correct 86 ms 181020 KB Output is correct
49 Correct 88 ms 180912 KB Output is correct
50 Correct 89 ms 181016 KB Output is correct
51 Correct 89 ms 181004 KB Output is correct
52 Correct 87 ms 180956 KB Output is correct
53 Correct 84 ms 181024 KB Output is correct
54 Correct 98 ms 188964 KB Output is correct
55 Correct 313 ms 241740 KB Output is correct
56 Correct 162 ms 225536 KB Output is correct
57 Correct 156 ms 225464 KB Output is correct
58 Correct 168 ms 225588 KB Output is correct
59 Correct 162 ms 225504 KB Output is correct
60 Correct 147 ms 225472 KB Output is correct
61 Correct 156 ms 225512 KB Output is correct
62 Correct 248 ms 232432 KB Output is correct
63 Correct 145 ms 225580 KB Output is correct
64 Correct 188 ms 225560 KB Output is correct
65 Correct 184 ms 225560 KB Output is correct
66 Correct 188 ms 225592 KB Output is correct
67 Correct 150 ms 225560 KB Output is correct

Subtask #6
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 178388 KB Output is correct
2 Correct 79 ms 178416 KB Output is correct
3 Correct 79 ms 178388 KB Output is correct
4 Correct 81 ms 178496 KB Output is correct
5 Correct 78 ms 178380 KB Output is correct
6 Correct 80 ms 178376 KB Output is correct
7 Correct 99 ms 178436 KB Output is correct
8 Correct 82 ms 178420 KB Output is correct
9 Correct 80 ms 178380 KB Output is correct
10 Correct 80 ms 178380 KB Output is correct
11 Correct 81 ms 178512 KB Output is correct
12 Correct 80 ms 178464 KB Output is correct
13 Correct 1074 ms 394212 KB Output is correct
14 Correct 1243 ms 431612 KB Output is correct
15 Correct 1556 ms 475672 KB Output is correct
16 Correct 1748 ms 526964 KB Output is correct
17 Correct 2154 ms 587400 KB Output is correct
18 Correct 2141 ms 587408 KB Output is correct
19 Correct 2127 ms 587444 KB Output is correct
20 Correct 80 ms 178456 KB Output is correct
21 Correct 80 ms 178440 KB Output is correct
22 Correct 85 ms 178436 KB Output is correct
23 Correct 81 ms 178444 KB Output is correct
24 Correct 81 ms 178492 KB Output is correct
25 Correct 82 ms 178440 KB Output is correct
26 Correct 83 ms 178516 KB Output is correct
27 Correct 93 ms 178420 KB Output is correct
28 Correct 81 ms 178448 KB Output is correct
29 Correct 82 ms 178536 KB Output is correct
30 Correct 81 ms 178540 KB Output is correct
31 Correct 81 ms 178452 KB Output is correct
32 Correct 83 ms 178548 KB Output is correct
33 Correct 87 ms 178408 KB Output is correct
34 Correct 84 ms 178424 KB Output is correct
35 Correct 98 ms 178460 KB Output is correct
36 Correct 88 ms 178508 KB Output is correct
37 Correct 86 ms 178352 KB Output is correct
38 Correct 87 ms 178564 KB Output is correct
39 Correct 79 ms 178528 KB Output is correct
40 Correct 80 ms 178600 KB Output is correct
41 Correct 83 ms 178628 KB Output is correct
42 Correct 81 ms 178508 KB Output is correct
43 Correct 96 ms 178604 KB Output is correct
44 Correct 84 ms 178596 KB Output is correct
45 Correct 85 ms 178596 KB Output is correct
46 Correct 88 ms 178624 KB Output is correct
47 Correct 91 ms 178568 KB Output is correct
48 Correct 86 ms 178508 KB Output is correct
49 Correct 82 ms 178620 KB Output is correct
50 Correct 82 ms 178536 KB Output is correct
51 Correct 94 ms 178404 KB Output is correct
52 Correct 83 ms 178356 KB Output is correct
53 Correct 83 ms 178388 KB Output is correct
54 Correct 83 ms 178476 KB Output is correct
55 Correct 83 ms 178520 KB Output is correct
56 Correct 83 ms 178520 KB Output is correct
57 Correct 86 ms 179032 KB Output is correct
58 Correct 93 ms 181296 KB Output is correct
59 Correct 93 ms 181004 KB Output is correct
60 Correct 84 ms 180928 KB Output is correct
61 Correct 86 ms 181020 KB Output is correct
62 Correct 86 ms 180968 KB Output is correct
63 Correct 89 ms 180896 KB Output is correct
64 Correct 88 ms 181104 KB Output is correct
65 Correct 86 ms 181020 KB Output is correct
66 Correct 88 ms 180912 KB Output is correct
67 Correct 89 ms 181016 KB Output is correct
68 Correct 89 ms 181004 KB Output is correct
69 Correct 87 ms 180956 KB Output is correct
70 Correct 84 ms 181024 KB Output is correct
71 Correct 98 ms 188964 KB Output is correct
72 Correct 313 ms 241740 KB Output is correct
73 Correct 162 ms 225536 KB Output is correct
74 Correct 156 ms 225464 KB Output is correct
75 Correct 168 ms 225588 KB Output is correct
76 Correct 162 ms 225504 KB Output is correct
77 Correct 147 ms 225472 KB Output is correct
78 Correct 156 ms 225512 KB Output is correct
79 Correct 248 ms 232432 KB Output is correct
80 Correct 145 ms 225580 KB Output is correct
81 Correct 188 ms 225560 KB Output is correct
82 Correct 184 ms 225560 KB Output is correct
83 Correct 188 ms 225592 KB Output is correct
84 Correct 150 ms 225560 KB Output is correct
85 Correct 308 ms 292496 KB Output is correct
86 Correct 652 ms 456848 KB Output is correct
87 Correct 557 ms 456780 KB Output is correct
88 Correct 503 ms 456900 KB Output is correct
89 Correct 489 ms 456756 KB Output is correct
90 Correct 513 ms 456780 KB Output is correct
91 Correct 864 ms 458484 KB Output is correct
92 Correct 1120 ms 478336 KB Output is correct
93 Correct 749 ms 456860 KB Output is correct
94 Correct 562 ms 457016 KB Output is correct
95 Correct 931 ms 457124 KB Output is correct
96 Correct 943 ms 457248 KB Output is correct
97 Correct 460 ms 456752 KB Output is correct