oj.uz

Submission #1076582

# Submission time Handle Problem Language Result Execution time Memory
1076582 2024-08-26T14:50:18 Z coldbr3w Copy and Paste 3 (JOI22_copypaste3) C++17
57 / 100
 3000 ms 579052 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()

const ll N = 3000;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 350;
ll n,a,b,c;
string s;
vector<int> z_function(string s) {
    int n = s.length();
    vector<int> z(n);
    int l = 0, r = 0;
    for (int i = 0; i < n; ++i) {
        if (i <= r) z[i] = min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        } 
    }
    return z;
}
struct ccjv{int l,r,cnt;};
int st[N][13];
ll dp[N][N];
vector<ccjv>adj[N][N];
ll get(ll l, ll r){
	ll p = 31 - __builtin_clz(r - l + 1);
	return max(st[l][p], st[r - (1 << p) + 1][p]);
}
void to_thic_cau(){ 
	cin >> n >> s >> a >> b >> c;
	s = " " + s;
	for(ll i = 1; i <= n;i++){
		for(ll j = 1; j <= n;j++) dp[i][j] = (j - i + 1) * a;
	}
	for(int i = 1; i <= n;i++){
		string t;
		for(int j = i; j <= n;j++) t += s[j];
		vector<int>z = z_function(t);
		int sz = (ll)t.size() - 1;
		for(int i = 0; i <= sz;i++) st[i][0] = z[i];
		for(int j = 1; j <= 12;j++){
			for(int i = 0; i + (1 << j) <= sz + 1;i++) st[i][j] = max(st[i][j-1], st[i + (1 << (j - 1))][j - 1]);
		}
		for(int len = 1; len <= sz;len++){
			int cnt = 0, idx = -1, fir = -1;
			while(1){
				int l = idx + 1, r = sz, pos = -1;
				while(l <= r){
					ll mid = (l + r) / 2;
					if(get(idx + 1, mid) >= len) pos = mid, r = mid - 1;
					else l = mid + 1;
				}
				if(pos == -1) break;
				if(fir == -1) fir = pos;
				idx = pos + len - 1, cnt++;
				adj[fir + i][idx + i].pb({fir + i, fir + len - 1 + i, cnt});
			}
		}
	}
	for(int len = 0; len <= n;len++){
		for(ll i = 1; i + len <= n;i++){
			ll j = i + len;
			for(auto x : adj[i][j]){
				ll l = x.l, r = x.r, cnt = x.cnt;
				if(l == i && r == j) continue;
				dp[i][j] = min(dp[i][j], ((j - i + 1) - (r - l + 1) * cnt) * a + b + dp[l][r] + c * cnt);
			}
			if(i - 1 >= 0) dp[i-1][j] = min(dp[i-1][j], dp[i][j] + a);
			if(j + 1 <= n) dp[i][j+1] = min(dp[i][j+1], dp[i][j] + a);
		}
	}
	cout << dp[1][n] << "\n";
}     

signed main()   
{  
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	ll tc = 1;
	//cin >> tc;
	while(tc--) to_thic_cau();
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 211752 KB Output is correct
2 Correct 146 ms 211788 KB Output is correct
3 Correct 123 ms 211692 KB Output is correct
4 Correct 111 ms 212048 KB Output is correct
5 Correct 114 ms 211744 KB Output is correct
6 Correct 114 ms 211644 KB Output is correct
7 Correct 114 ms 211792 KB Output is correct
8 Correct 109 ms 211792 KB Output is correct
9 Correct 113 ms 211796 KB Output is correct
10 Correct 113 ms 211688 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 211796 KB Output is correct
2 Correct 113 ms 211792 KB Output is correct
3 Correct 1711 ms 437492 KB Output is correct
4 Correct 2206 ms 477176 KB Output is correct
5 Correct 2566 ms 524316 KB Output is correct
6 Execution timed out 3071 ms 579052 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 211752 KB Output is correct
2 Correct 146 ms 211788 KB Output is correct
3 Correct 123 ms 211692 KB Output is correct
4 Correct 111 ms 212048 KB Output is correct
5 Correct 114 ms 211744 KB Output is correct
6 Correct 114 ms 211644 KB Output is correct
7 Correct 114 ms 211792 KB Output is correct
8 Correct 109 ms 211792 KB Output is correct
9 Correct 113 ms 211796 KB Output is correct
10 Correct 113 ms 211688 KB Output is correct
11 Correct 115 ms 211820 KB Output is correct
12 Correct 117 ms 211792 KB Output is correct
13 Correct 119 ms 211884 KB Output is correct
14 Correct 107 ms 211584 KB Output is correct
15 Correct 112 ms 211796 KB Output is correct
16 Correct 114 ms 211796 KB Output is correct
17 Correct 115 ms 211792 KB Output is correct
18 Correct 114 ms 211628 KB Output is correct
19 Correct 112 ms 211796 KB Output is correct
20 Correct 116 ms 211796 KB Output is correct
21 Correct 109 ms 212052 KB Output is correct
22 Correct 113 ms 211796 KB Output is correct
23 Correct 112 ms 211796 KB Output is correct
24 Correct 116 ms 211932 KB Output is correct
25 Correct 116 ms 211884 KB Output is correct
26 Correct 116 ms 211796 KB Output is correct
27 Correct 113 ms 211940 KB Output is correct
28 Correct 113 ms 211792 KB Output is correct
29 Correct 119 ms 211928 KB Output is correct
30 Correct 112 ms 211792 KB Output is correct
31 Correct 111 ms 211940 KB Output is correct
32 Correct 110 ms 211920 KB Output is correct
33 Correct 117 ms 211792 KB Output is correct
34 Correct 112 ms 211792 KB Output is correct
35 Correct 113 ms 211800 KB Output is correct
36 Correct 112 ms 211792 KB Output is correct
37 Correct 115 ms 211836 KB Output is correct
38 Correct 115 ms 211684 KB Output is correct
39 Correct 111 ms 211796 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 211752 KB Output is correct
2 Correct 146 ms 211788 KB Output is correct
3 Correct 123 ms 211692 KB Output is correct
4 Correct 111 ms 212048 KB Output is correct
5 Correct 114 ms 211744 KB Output is correct
6 Correct 114 ms 211644 KB Output is correct
7 Correct 114 ms 211792 KB Output is correct
8 Correct 109 ms 211792 KB Output is correct
9 Correct 113 ms 211796 KB Output is correct
10 Correct 113 ms 211688 KB Output is correct
11 Correct 115 ms 211820 KB Output is correct
12 Correct 117 ms 211792 KB Output is correct
13 Correct 119 ms 211884 KB Output is correct
14 Correct 107 ms 211584 KB Output is correct
15 Correct 112 ms 211796 KB Output is correct
16 Correct 114 ms 211796 KB Output is correct
17 Correct 115 ms 211792 KB Output is correct
18 Correct 114 ms 211628 KB Output is correct
19 Correct 112 ms 211796 KB Output is correct
20 Correct 116 ms 211796 KB Output is correct
21 Correct 109 ms 212052 KB Output is correct
22 Correct 113 ms 211796 KB Output is correct
23 Correct 112 ms 211796 KB Output is correct
24 Correct 116 ms 211932 KB Output is correct
25 Correct 116 ms 211884 KB Output is correct
26 Correct 116 ms 211796 KB Output is correct
27 Correct 113 ms 211940 KB Output is correct
28 Correct 113 ms 211792 KB Output is correct
29 Correct 119 ms 211928 KB Output is correct
30 Correct 112 ms 211792 KB Output is correct
31 Correct 111 ms 211940 KB Output is correct
32 Correct 110 ms 211920 KB Output is correct
33 Correct 117 ms 211792 KB Output is correct
34 Correct 112 ms 211792 KB Output is correct
35 Correct 113 ms 211800 KB Output is correct
36 Correct 112 ms 211792 KB Output is correct
37 Correct 115 ms 211836 KB Output is correct
38 Correct 115 ms 211684 KB Output is correct
39 Correct 111 ms 211796 KB Output is correct
40 Correct 112 ms 212220 KB Output is correct
41 Correct 121 ms 214608 KB Output is correct
42 Correct 109 ms 213596 KB Output is correct
43 Correct 118 ms 213588 KB Output is correct
44 Correct 119 ms 213584 KB Output is correct
45 Correct 121 ms 213492 KB Output is correct
46 Correct 109 ms 213584 KB Output is correct
47 Correct 122 ms 213672 KB Output is correct
48 Correct 113 ms 213584 KB Output is correct
49 Correct 136 ms 213588 KB Output is correct
50 Correct 115 ms 213588 KB Output is correct
51 Correct 118 ms 213844 KB Output is correct
52 Correct 121 ms 213764 KB Output is correct
53 Correct 116 ms 213588 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 211752 KB Output is correct
2 Correct 146 ms 211788 KB Output is correct
3 Correct 123 ms 211692 KB Output is correct
4 Correct 111 ms 212048 KB Output is correct
5 Correct 114 ms 211744 KB Output is correct
6 Correct 114 ms 211644 KB Output is correct
7 Correct 114 ms 211792 KB Output is correct
8 Correct 109 ms 211792 KB Output is correct
9 Correct 113 ms 211796 KB Output is correct
10 Correct 113 ms 211688 KB Output is correct
11 Correct 115 ms 211820 KB Output is correct
12 Correct 117 ms 211792 KB Output is correct
13 Correct 119 ms 211884 KB Output is correct
14 Correct 107 ms 211584 KB Output is correct
15 Correct 112 ms 211796 KB Output is correct
16 Correct 114 ms 211796 KB Output is correct
17 Correct 115 ms 211792 KB Output is correct
18 Correct 114 ms 211628 KB Output is correct
19 Correct 112 ms 211796 KB Output is correct
20 Correct 116 ms 211796 KB Output is correct
21 Correct 109 ms 212052 KB Output is correct
22 Correct 113 ms 211796 KB Output is correct
23 Correct 112 ms 211796 KB Output is correct
24 Correct 116 ms 211932 KB Output is correct
25 Correct 116 ms 211884 KB Output is correct
26 Correct 116 ms 211796 KB Output is correct
27 Correct 113 ms 211940 KB Output is correct
28 Correct 113 ms 211792 KB Output is correct
29 Correct 119 ms 211928 KB Output is correct
30 Correct 112 ms 211792 KB Output is correct
31 Correct 111 ms 211940 KB Output is correct
32 Correct 110 ms 211920 KB Output is correct
33 Correct 117 ms 211792 KB Output is correct
34 Correct 112 ms 211792 KB Output is correct
35 Correct 113 ms 211800 KB Output is correct
36 Correct 112 ms 211792 KB Output is correct
37 Correct 115 ms 211836 KB Output is correct
38 Correct 115 ms 211684 KB Output is correct
39 Correct 111 ms 211796 KB Output is correct
40 Correct 112 ms 212220 KB Output is correct
41 Correct 121 ms 214608 KB Output is correct
42 Correct 109 ms 213596 KB Output is correct
43 Correct 118 ms 213588 KB Output is correct
44 Correct 119 ms 213584 KB Output is correct
45 Correct 121 ms 213492 KB Output is correct
46 Correct 109 ms 213584 KB Output is correct
47 Correct 122 ms 213672 KB Output is correct
48 Correct 113 ms 213584 KB Output is correct
49 Correct 136 ms 213588 KB Output is correct
50 Correct 115 ms 213588 KB Output is correct
51 Correct 118 ms 213844 KB Output is correct
52 Correct 121 ms 213764 KB Output is correct
53 Correct 116 ms 213588 KB Output is correct
54 Correct 137 ms 218704 KB Output is correct
55 Correct 505 ms 276712 KB Output is correct
56 Correct 228 ms 242260 KB Output is correct
57 Correct 205 ms 240008 KB Output is correct
58 Correct 190 ms 239400 KB Output is correct
59 Correct 184 ms 239404 KB Output is correct
60 Correct 175 ms 239188 KB Output is correct
61 Correct 217 ms 240720 KB Output is correct
62 Correct 415 ms 268624 KB Output is correct
63 Correct 211 ms 240220 KB Output is correct
64 Correct 235 ms 241744 KB Output is correct
65 Correct 338 ms 255960 KB Output is correct
66 Correct 334 ms 255780 KB Output is correct
67 Correct 188 ms 239184 KB Output is correct

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 211752 KB Output is correct
2 Correct 146 ms 211788 KB Output is correct
3 Correct 123 ms 211692 KB Output is correct
4 Correct 111 ms 212048 KB Output is correct
5 Correct 114 ms 211744 KB Output is correct
6 Correct 114 ms 211644 KB Output is correct
7 Correct 114 ms 211792 KB Output is correct
8 Correct 109 ms 211792 KB Output is correct
9 Correct 113 ms 211796 KB Output is correct
10 Correct 113 ms 211688 KB Output is correct
11 Correct 115 ms 211796 KB Output is correct
12 Correct 113 ms 211792 KB Output is correct
13 Correct 1711 ms 437492 KB Output is correct
14 Correct 2206 ms 477176 KB Output is correct
15 Correct 2566 ms 524316 KB Output is correct
16 Execution timed out 3071 ms 579052 KB Time limit exceeded
17 Halted 0 ms 0 KB -