QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#590761#562. 码农Crying100 ✓50ms16352kbC++143.2kb2024-09-26 11:07:062024-09-26 11:07:06

Judging History

你现在查看的是最新测评结果

  • [2024-09-26 11:07:06]
  • 评测
  • 测评结果:100
  • 用时:50ms
  • 内存:16352kb
  • [2024-09-26 11:07:06]
  • 提交

answer

#include<bits/stdc++.h>
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
const int N = 1e5+10,M = 10,INF = 1e9;
template<typename T>void tomin(T& x,T y){x = min(x,y);}
template<typename T>void tomax(T& x,T y){x = max(x,y);}
//
int n,c[M],tc,tp;
char s[N];

int m,sa[N],rk[N*2],oldrk[N*2],cnt[N],tmp[N],tot;
int st[20][N];

int lcp(int i,int j){
    assert(i != j);
    i = rk[i],j = rk[j]; if(i>j)swap(i,j);
    i++; int len = __lg(j-i+1);
    return min(st[len][i],st[len][j-(1<<len)+1]);
}

struct Seg{
    int t[N<<2];
    void pu(int x){ t[x] = min(t[lc(x)],t[rc(x)]); }
    void build(int x,int l,int r){
        if(l==r)return t[x] = sa[l],void();
        build(lc(x),l,mid); build(rc(x),mid+1,r);
        pu(x);
    }
    int qpre(int x,int l,int r,int pos,int v){
        if(l>=pos || t[x]>v)return l-1;
        if(l==r)return l;
        int res = qpre(rc(x),mid+1,r,pos,v); if(res != mid)return res;
        return qpre(lc(x),l,mid,pos,v);
    }
    int qsuf(int x,int l,int r,int pos,int v){
        if(r<=pos || t[x]>v)return r+1;
        if(l==r)return r;
        int res = qsuf(lc(x),l,mid,pos,v); if(res != mid+1)return res;
        return qsuf(rc(x),mid+1,r,pos,v);
    }
}seg;
int chk(int l,int r){
    int len = r-l+1;
    int p = seg.qpre(1,1,n,rk[l],l-len),q = seg.qsuf(1,1,n,rk[l],l-len);
    if(p && lcp(sa[p],l) >= len)return 1;
    if(q!=n+1 && lcp(l,sa[q]) >= len)return 1;
    return 0;
}

void build(){
    m = max(n,150); 
    for(int i=1;i<=n;i++)rk[i] = s[i],cnt[rk[i]]++;
    for(int i=1;i<=m;i++)cnt[i] += cnt[i-1];
    for(int i=n;i>=1;i--)sa[cnt[rk[i]]--] = i;

    for(int w=1;w<n;w<<=1){
        tot = 0; 
        for(int i=n-w+1;i<=n;i++)tmp[++tot] = i;
        for(int i=1;i<=n;i++)if(sa[i] > w)tmp[++tot] = sa[i] - w;
        memset(cnt,0,sizeof cnt);
        for(int i=1;i<=n;i++)cnt[rk[i]]++;
        for(int i=1;i<=m;i++)cnt[i] += cnt[i-1];
        for(int i=n;i>=1;i--)sa[cnt[rk[tmp[i]]]--] = tmp[i];
        memcpy(oldrk,rk,sizeof oldrk);
        rk[sa[1]] = 1;
        for(int i=2;i<=n;i++){
            rk[sa[i]] = rk[sa[i-1]];
            if(oldrk[sa[i]] != oldrk[sa[i-1]] || oldrk[sa[i]+w] != oldrk[sa[i-1]+w])rk[sa[i]]++;
        }
    }
    //
    for(int i=1,j=0;i<=n;i++){
        if(j)j--;
        while(s[i+j] == s[sa[rk[i]-1]+j])j++;
        st[0][rk[i]] = j;
    }
    for(int j=1;j<20;j++)for(int i=1;i<=n-(1<<j)+1;i++)st[j][i] = min(st[j-1][i],st[j-1][i+(1<<(j-1))]);
}

int dp[N],qu[N],hd,rr;
int w(int j){return dp[j] - j*tc;}

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

    cin>>(s+1); n = strlen(s+1);
    for(int i=0;i<M;i++)cin>>c[i];
    cin>>tc>>tp;

    if(n==1){
        cout<<c[s[1]-'0']; exit(0);
    }
    build();    
    seg.build(1,1,n);

    int j = 1;
    for(int i=1;i<=n;i++){
        dp[i] = dp[i-1] + c[s[i]-'0'];
        while(j<=i && !chk(j,i))j++;

        while(hd<rr && w(qu[rr-1]) >= w(i-1))rr--;
        qu[rr++] = i-1;
        while(hd<rr && qu[hd]<j-1)hd++;
        if(hd<rr){
            int k = qu[hd];
            tomin(dp[i],dp[k] + tc*(i-k) + tp);
        }
    }

    cout<<dp[n]<<endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 0ms
memory: 9648kb

input:

75902254188305020153265646636543016308121578993465
861 520 899 835 182 401 640 780 136 282
50 500

output:

20968

result:

ok answer is '20968'

Test #2:

score: 10
Accepted
time: 0ms
memory: 13812kb

input:

0604099983365439103293148513340002146605464429999987780100621387726951980692690201398795518328124417
258 958 925 647 415 662 591 225 294 761
1 1

output:

5889

result:

ok answer is '5889'

Test #3:

score: 10
Accepted
time: 0ms
memory: 13852kb

input:

08218913670165447723153562370549386381711380431842858277022719973080819387485328444919681527790176060627303826546247484140477434828672640479794131501115583983463596800484713238900414170161023324262261
679 478 803 834 961 954 269 432 740 101
1 2000

output:

126123

result:

ok answer is '126123'

Test #4:

score: 10
Accepted
time: 4ms
memory: 13880kb

input:

105317817326678173266278173266781861452966757817326678173266278886145296675781732667817326646678173266274192117326678173266784326678173266466781732662741921173271467739032664667817326627419211244018646678173266274192667817326627419211732667817326678432667817326646676064694317326627419211732667817326...

output:

1258663

result:

ok answer is '1258663'

Test #5:

score: 10
Accepted
time: 8ms
memory: 16016kb

input:

010101010101310101000101010101010101010101015194010101410101310101010101016101050901010101010101010101010101010121010101010301010101010101050101010131010401019101030101010101010106010101010101010301113101010101060101010101010221310101010101010101010201010101010101010101010101010201010101010101010301...

output:

634386

result:

ok answer is '634386'

Test #6:

score: 10
Accepted
time: 38ms
memory: 15464kb

input:

101101011011010110101101101011011010110101101101011010110110101101101011010110110101101101011010110110101101011011010110110101101011011010110101101101011011010110101101101011011010110101101101011010110110101101101011010110110101101101011010110110101101011011010110110101101011011010110101101101011011...

output:

3608448

result:

ok answer is '3608448'

Test #7:

score: 10
Accepted
time: 50ms
memory: 16180kb

input:

259056990780332590569987271259056990780332590569949056998727125905699078033259056998286994905632095600332590569982253590569907803325905699872712590569907803325905699490569987271259056990780332590569982869949056320956003325905699822589490569987271259056990780332590569982869949056320956003325905699822...

output:

46857468

result:

ok answer is '46857468'

Test #8:

score: 10
Accepted
time: 45ms
memory: 16352kb

input:

228255514297409372831124051231457518830714580983978118191715409980887870392763255958771396014724099273225818044544335318830714580983978118191715409980887870392763255958771396014724099273222875394216198066164777774453584645720613199953220643394961533112597700983978118191715409980887870392763255958771...

output:

38860522

result:

ok answer is '38860522'

Test #9:

score: 10
Accepted
time: 39ms
memory: 15808kb

input:

559026120443215529932053298946836947788255576080102636079256978346848066124067848713074979476892430650387372942634392777955392777605987788887027251714708216083863607925697834949925247190947471443668150708082380654358861507758294311830016300385819376425818027205596619887481716476691219729850438192848...

output:

34081603

result:

ok answer is '34081603'

Test #10:

score: 10
Accepted
time: 43ms
memory: 15820kb

input:

010101010101010101010101010101010101000101010101010101010101010101010101010101010103010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101015101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010601010101010101...

output:

3071979

result:

ok answer is '3071979'