Submission #711206

#	Time	Username	Problem	Language	Result	Execution time	Memory
711206		konstantys	Copy and Paste 3 (JOI22_copypaste3)	C++14	100 / 100	374 ms	34036 KiB

copypaste3

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<map>
#define duzo 1000000000000000LL
using namespace std;
map<long long,int> mp;
string s;
int n,m;
long long a,b,c,dp[2501][2501],k,l;
long long st,st2;
short lst[30],kol[2501],kol2[2501],kol3[2501][30],przed[2501];
int main(){
  ios_base::sync_with_stdio(0);
  //cerr<<modpow(base,MOD2-2,MOD2);
  cin>>n;
  cin>>s;
  cin>>a>>b>>c;
  st=1;
  st2=1;
  for(int i=n-1;i>=0;i--){
    dp[i][i]=a-duzo;
    kol[i]=n-lst[((char)s[i])-'a'];
    kol2[i]=kol[i];
    lst[((char)s[i])-'a']=n-i;
  }
  kol2[n]=n;
  kol[n]=n;
  for(int i=1;i<n;i++){
    //cerr<<kol[0]<<"\n";
    //cout<<dp[0][n-1]+duzo<<"???\n";
    for(int u=0;u<n-i;u++){
      dp[u][u+i]=min(dp[u][u+i],a+min(dp[u][u+i-1],dp[u+1][u+i]));
    }
    //cerr<<dp[0][n-1]+duzo<<"!!!\n";
    for(int u=0;u<=n-i;u++){
      if(kol[u]==n) continue;
      //if(u==1) cerr<<i<<" "<<u<<" "<<kol[u]<<"\n";
      m=kol[u];
      l=m-(u+i);
      k=dp[u][u+i-1];
      k+=b+c;
      while(m!=n){
        k+=c;
        dp[u][m+i-1]=min(dp[u][m+i-1],k+l*a);
        //if(dp[0][n-1]+duzo==363) cerr<<u<<" "<<u+i-1<<"!!!";
        //cerr<<k+duzo<<" "<<l*a<<"  "<<m<<" "<<kol[m]<<"  "<<i<<"\n";
        l+=kol[m]-m-i;
        m=kol[m];
      }
    }
    for(int u=n-i-1;u>=0;u--){
      if(kol2[u]+i<n)
        for(int j=0;j<26;j++) kol3[u][j]=kol3[kol2[u]][j];
      else
        for(int j=0;j<26;j++) kol3[u][j]=n;
      kol2[u]=kol3[u][((char)s[u+i]-'a')];
      kol3[u][((char)s[u+i]-'a')]=u;
      przed[kol2[u]]=-u-2;
      //cerr<<przed[u]<<" "<<kol2[u]<<"- ";
      //cerr<<kol2[u];
    }
    //cerr<<"\n";
    kol2[n-i]=n;
    kol[n-i]=n;
    for(int u=0;u<n-i;u++){
      //cerr<<przed[u]<<" "<<kol2[u]<<", ";
      if(przed[u]<-1) przed[u]=-przed[u]-2; else przed[u]=-1;
      if(przed[u]==-1)
        kol[u]=u;
      else
        kol[u]=kol[przed[u]];
      //cerr<<kol2[0]<<"\n";
      while(kol[u]<=u+i) kol[u]=kol2[kol[u]];
    }
    //cerr<<"\n";
    //cerr<<"AA";
  }
  cout<<dp[0][n-1]+duzo;
  return 0;
}

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