oj.uz

Submission #711175

# Submission time Handle Problem Language Result Execution time Memory
711175 2023-03-16T09:19:26 Z konstantys Copy and Paste 3 (JOI22_copypaste3) C++14
1 / 100
 2025 ms 23672 KB 
#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;
      ///cerr<<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);
        //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')];
      przed[kol2[u]]=-u;
      kol3[u][((char)s[u+i]-'a')]=u;
      if(przed[u]<0) przed[u]=-przed[u]; else przed[u]=-1;
    }
    kol2[n-i]=n;
    kol[n-i]=n;
    for(int u=0;u<n-i;u++){
      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<<"AA";
  }
  cout<<dp[0][n-1]+duzo;
  return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2025 ms 20852 KB Output is correct
4 Incorrect 2001 ms 23672 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Incorrect 1 ms 324 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Incorrect 1 ms 324 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Incorrect 1 ms 324 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2025 ms 20852 KB Output is correct
14 Incorrect 2001 ms 23672 KB Output isn't correct
15 Halted 0 ms 0 KB -