Submission #972713

#	Time	Username	Problem	Language	Result	Execution time	Memory
972713		happy_node	Copy and Paste 3 (JOI22_copypaste3)	C++17	62 / 100	409 ms	161732 KiB

copypaste3

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MX=2505;

int N, A, B, C;
string s;
ll dp[MX][MX];

const ll P=1e9+93, mod=2'147'483'647;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll hsh[MX][MX], pw[MX], key[MX];

int nxt[MX][MX];

bool ok(int a, int b, int l, int r) {
	if(l<=b) return false;
	return hsh[a][b]==hsh[l][r];
}

vector<pair<ll,ll>> v[MX];

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	for(int i=0;i<MX;i++)
		for(int j=i;j<MX;j++)
			dp[i][j]=2e18;

	pw[0]=1;
	for(int i=1;i<MX;i++) pw[i]=pw[i-1]*P%mod;

	cin>>N;
	cin>>s;
	cin>>A>>B>>C;

	s='#'+s;

	for(int c=0;c<26;c++) key[c]=rng()%mod;

	for(int l=1;l<=N;l++) {
		for(int r=l;r<=N;r++) {
			int p=r-l+1;
			hsh[l][r]=hsh[l][r-1]+pw[p]*(key[s[r]-'a'])%mod;
			hsh[l][r]%=mod;
			v[p].push_back({hsh[l][r],l});
		}
	}

	for(int i=1;i<=N;i++) {
		sort(v[i].begin(),v[i].end());

		int k=0;
		for(int j=0;j<v[i].size();j++) {
			if(k<j) k++;

			while(k<v[i].size() && v[i][k+1].first==v[i][k].first 
				&& v[i][k].second<v[i][j].second+i) {
				k++;
			}	
			if(k>=v[i].size()) {
				nxt[v[i][j].second][v[i][j].second+i-1]= -1;
				continue;
			}
			if(v[i][k].second<v[i][j].second+i) {
				nxt[v[i][j].second][v[i][j].second+i-1]= -1;
				continue;
			}
			nxt[v[i][j].second][v[i][j].second+i-1]=v[i][k].second;
		}
	}

	for(int l=N;l>0;l--) {
		for(int r=l;r<=N;r++) {
			dp[l][r]=min(dp[l][r],dp[l][r-1]+A);

			ll k=nxt[l][r], p=r-l+1, z=1;

			while(k!=-1) {
				z++;
				ll len=k+p-1-l+1;
				dp[l][k+p-1]=min(dp[l][k+p-1],dp[l][r]+z*C+B+(len-p*z)*A);
				k=nxt[k][k+p-1];
			}

			dp[l-1][r]=min(dp[l-1][r],dp[l][r]+A);
		}
	}

	cout<<dp[1][N]<<'\n';

}

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:58:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(int j=0;j<v[i].size();j++) {
      |               ~^~~~~~~~~~~~
copypaste3.cpp:61:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |    while(k<v[i].size() && v[i][k+1].first==v[i][k].first
      |          ~^~~~~~~~~~~~
copypaste3.cpp:65:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |    if(k>=v[i].size()) {
      |       ~^~~~~~~~~~~~~

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