Submission #30765936

---

Source Code Expand

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int Mt=1e5,N=2.5e3+10,base=23333,inf=1e18;
int n,a,b,c,pw[N],hs[N],f[N][N];string s;
inline char getc(){
    static char buf[Mt],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mt,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int r=0,f=1;char c=getc();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getc();}
    while(c<='9'&&c>='0') r=(r<<1)+(r<<3)+(c^48),c=getc();
    return r*f;
}
inline string sread(){
    string s="";char c=getc();
    while(c<'a'||c>'z') c=getc();
    while(c<='z'&&c>='a') s+=c,c=getc();
    return s;
}
void put(int x){
    if(x<0){putchar('-');x=~x+1;}
    if(x>9) put(x/10);
    putchar(x%10+'0');
}
int min(int x,int y){return x<y?x:y;}
void chkmn(int &x,int y){x=min(x,y);}
signed main(){
//    freopen("cpp.in","r",stdin);
//    freopen("cpp.out","w",stdout);
    n=read(),s=sread(),a=read(),b=read(),c=read(),pw[0]=1;
    for(int i=1;i<=n;i++) hs[i]=hs[i-1]*base+(s[i-1]-'a'+1),pw[i]=pw[i-1]*base;
    for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) f[i][j]=inf;
    for(int i=1;i<=n;i++) f[i][i]=a;
    for(int len=1;len<=n;len++) for(int l=1,r,hs1;l+len-1<=n;l++){
        r=l+len-1,hs1=hs[r]-hs[l-1]*pw[len],chkmn(f[l][r],f[l+1][r]+a),chkmn(f[l][r],f[l][r-1]+a);
        int cnt=1;
        for(int nl=r+1,nr,hs2;nl+len-1<=n;nl++){
            nr=nl+len-1,hs2=hs[nr]-hs[nl-1]*pw[len];
            if(hs1==hs2)chkmn(f[l][nr],f[l][r]+(nl-l-len*cnt)*a+b+(cnt+1)*c),cnt++,nl=nr;
        }
    }
    return put(f[1][n]),puts(""),0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void put(long long unsigned int)’:
./Main.cpp:23:9: warning: comparison of unsigned expression < 0 is always false [-Wtype-limits]
   23 |     if(x<0){putchar('-');x=~x+1;}
      |        ~^~

Judge Result