oj.uz

Submission #1076648

# Submission time Handle Problem Language Result Execution time Memory
1076648 2024-08-26T15:16:48 Z coldbr3w Copy and Paste 3 (JOI22_copypaste3) C++17
1 / 100
 122 ms 211796 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][12];
ll dp[N][N], lg[N];
vector<ccjv>adj[N][N];
int get(int l, int r){
	int p = lg[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(int i = 1; i <= n;i++) lg[i] = __lg(i);
	for(int i = 1; i <= n;i++){
		for(int j = i; j <= n;j++) dp[i][j] = 1ll * (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 <= lg[sz];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]);
		}
		ll mx = get(0, sz);
		for(int len = 1; len <= mx;len++){
			int cnt = 0, idx = -1, fir = -1;
			while(1){
				int l = idx + 1, r = sz, pos = -1;
				while(l <= r){
					int 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(int i = 1; i + len <= n;i++){
			int j = i + len;
			for(auto x : adj[i][j]){
				int l = x.l, r = x.r, cnt = x.cnt;
				if(l == i && r == j) continue;
				dp[i][j] = min(dp[i][j], (1ll * (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);
	ll tc = 1;
	//cin >> tc;
	while(tc--) to_thic_cau();
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 211796 KB Output is correct
2 Correct 120 ms 211704 KB Output is correct
3 Correct 115 ms 211796 KB Output is correct
4 Correct 98 ms 211600 KB Output is correct
5 Correct 96 ms 211792 KB Output is correct
6 Correct 101 ms 211736 KB Output is correct
7 Correct 103 ms 211796 KB Output is correct
8 Correct 106 ms 211740 KB Output is correct
9 Correct 98 ms 211796 KB Output is correct
10 Correct 100 ms 211796 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 100 ms 211788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 211796 KB Output is correct
2 Correct 120 ms 211704 KB Output is correct
3 Correct 115 ms 211796 KB Output is correct
4 Correct 98 ms 211600 KB Output is correct
5 Correct 96 ms 211792 KB Output is correct
6 Correct 101 ms 211736 KB Output is correct
7 Correct 103 ms 211796 KB Output is correct
8 Correct 106 ms 211740 KB Output is correct
9 Correct 98 ms 211796 KB Output is correct
10 Correct 100 ms 211796 KB Output is correct
11 Correct 100 ms 211792 KB Output is correct
12 Incorrect 101 ms 211792 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 211796 KB Output is correct
2 Correct 120 ms 211704 KB Output is correct
3 Correct 115 ms 211796 KB Output is correct
4 Correct 98 ms 211600 KB Output is correct
5 Correct 96 ms 211792 KB Output is correct
6 Correct 101 ms 211736 KB Output is correct
7 Correct 103 ms 211796 KB Output is correct
8 Correct 106 ms 211740 KB Output is correct
9 Correct 98 ms 211796 KB Output is correct
10 Correct 100 ms 211796 KB Output is correct
11 Correct 100 ms 211792 KB Output is correct
12 Incorrect 101 ms 211792 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 211796 KB Output is correct
2 Correct 120 ms 211704 KB Output is correct
3 Correct 115 ms 211796 KB Output is correct
4 Correct 98 ms 211600 KB Output is correct
5 Correct 96 ms 211792 KB Output is correct
6 Correct 101 ms 211736 KB Output is correct
7 Correct 103 ms 211796 KB Output is correct
8 Correct 106 ms 211740 KB Output is correct
9 Correct 98 ms 211796 KB Output is correct
10 Correct 100 ms 211796 KB Output is correct
11 Correct 100 ms 211792 KB Output is correct
12 Incorrect 101 ms 211792 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 211796 KB Output is correct
2 Correct 120 ms 211704 KB Output is correct
3 Correct 115 ms 211796 KB Output is correct
4 Correct 98 ms 211600 KB Output is correct
5 Correct 96 ms 211792 KB Output is correct
6 Correct 101 ms 211736 KB Output is correct
7 Correct 103 ms 211796 KB Output is correct
8 Correct 106 ms 211740 KB Output is correct
9 Correct 98 ms 211796 KB Output is correct
10 Correct 100 ms 211796 KB Output is correct
11 Incorrect 100 ms 211788 KB Output isn't correct
12 Halted 0 ms 0 KB -