Submission #897215

#	Time	Username	Problem	Language	Result	Execution time	Memory
897215		PoPularPlusPlus	Copy and Paste 3 (JOI22_copypaste3)	C++17	62 / 100	542 ms	122896 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 ll mod = 1000000000100011;

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

const ll P = 59;

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

void solve(){
	int n;
	cin >> n;
	string s;
	cin >> s;
	ll 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;
		}
	}

	ll hash_val[n][n];

	for(int l = 0; l < n; l++)
	{
		hash_val[l][l] = (s[l] - 'a' + 1);
		for(int r = l+1; r < n; r++)
		{
			hash_val[l][r] = (hash_val[l][r-1] * P  +  (s[r] - 'a' + 1)) % mod;
		}
	
	}

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

	for(int len = 0; len < n; len++){
		vector<pair<int,int>> v;
		for(int i = 0; i + len < n; i++){
			v.pb(mp(hash_val[i][i+len],i));
		}
		sort(all(v));

		while(v.size()){

			int hash = v.back().vf;

			for(int i = v.size()-1; i >= 0 && v[i].vf == hash; i--){
				while(v.size() > i + 2 && v[v.size()-2].vs > v[i].vs + len)
					v.pop_back();

				if(v.back().vs > v[i].vs + len)
					next[v[i].vs][v[i].vs+len] = v.back().vs;
			}

			while(v.size() && v.back().vf == hash)
				v.pop_back();
		}
	}

	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:60:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |     while(v.size() > i + 2 && v[v.size()-2].vs > v[i].vs + len)
      |           ~~~~~~~~~^~~~~~~

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