Submission #897198

#	Time	Username	Problem	Language	Result	Execution time	Memory
897198		PoPularPlusPlus	Copy and Paste 3 (JOI22_copypaste3)	C++17	62 / 100	3068 ms	455608 KiB

copypaste3

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define vf first 
#define vs second
const int mod = 998244353;

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int P = 71;

int convert(char c){
	return (c-'a') + 1;
}

void solve(){
	int n;
	cin >> n;
	string s;
	cin >> s;
	int a , b , c;
	cin >> a >> b >> c;
	ll dp[n][n];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			dp[i][j] = 1e18;
		}
	}

	map<pair<int,int> , int> m;

	vector<int> v[n*n];
	int cur = 0;

	int hash_val[n][n] , hash_pos[n][n];

	for(int i = 0; i < n; i++){
		ll pow = 1;
		ll hash = 0;
		for(int j = i; j < n; j++){
			hash += convert(s[j]) * pow;
			pow *= P;
			hash %= mod;
			pow %= mod;
			hash_val[i][j] = hash;
			if(m.find(mp(hash,j-i+1)) == m.end()){
				m[mp(hash,j-i+1)] = cur++;
			}
			hash_pos[i][j] = m[mp(hash,j-i+1)];
			v[hash_pos[i][j]].pb(i);
		}
	}

	for(int i = 0; i < cur; i++){
		sort(all(v[i]));
	}

	int next[n][n];
	memset(next,-1,sizeof next);

	for(int i = 0; i < n; i++){
		for(int j = i; j < n; j++){
			int pos = upper_bound(all(v[hash_pos[i][j]]),j) - v[hash_pos[i][j]].begin();
			if(pos < v[hash_pos[i][j]].size()){
				next[i][j] = v[hash_pos[i][j]][pos];
			}
		}
	}

	for(int len = 0; len < n; len++){
		for(int i = 0; i + len < n; i++){
			int j = i + len;
			dp[i][j] = min(dp[i][j],(len+1LL)*a);
			if(len > 0){
				dp[i][j] = min(dp[i][j] , min(dp[i+1][j] , dp[i][j-1]) + a);
			}
			ll val = dp[i][j] + b;
			val += c;
			int x = i , y = j;
			while(next[x][y] != -1){
				int pos = next[x][y];
				val += c;
				val += (pos - (y + 1LL))*a;
				dp[i][pos + len] = min(dp[i][pos+len],val);
				x = pos;
				y = pos + len;
			}
		}
	}

	cout << dp[0][n-1] << '\n';
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//int t;cin>>t;
	//while(t--)
		solve();
	return 0;
}

Compilation message (stderr)

copypaste3.cpp: In function 'void solve()':
copypaste3.cpp:67:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |    if(pos < v[hash_pos[i][j]].size()){
      |       ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
copypaste3.cpp:38:6: warning: variable 'hash_val' set but not used [-Wunused-but-set-variable]
   38 |  int hash_val[n][n] , hash_pos[n][n];
      |      ^~~~~~~~

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