QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#592996#562. 码农xlwang100 ✓26ms24932kbC++143.0kb2024-09-27 10:59:552024-09-27 10:59:56

Judging History

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

  • [2024-09-27 10:59:56]
  • 评测
  • 测评结果:100
  • 用时:26ms
  • 内存:24932kb
  • [2024-09-27 10:59:55]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define fr(i,j,k) for(register int i=j;i<=k;++i)
#define rf(i,j,k) for(register int i=j;i>=k;--i)
#define foredge(i,j) for(register int i=head[j];i;i=e[i].nxt)
#define pb push_back
#define Times printf("Time:%.3lf\n",clock()/CLOCKS_PER_SEC)
#define pii pair<int,int>
#define mk make_pair
using namespace std;
inline int read(){
	int x=0;
	bool f=0;
	char c=getchar();
	while(!isdigit(c)) f|=(c=='-'),c=getchar();
	while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return f?-x:x;
}
inline void write(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline void writeln(int x){write(x); puts("");}
inline void writepl(int x){write(x); putchar(' ');}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline int randfind(int l,int r){return rnd()%(r-l+1)+l;}
//inline void init(){
//	int t=read();
//	while(t--) work();
//}
const int Maxn=1e5+10;
struct node{
    int ch[10];
    int link;
    int ln;
}e[Maxn<<1];
int nod=1,lst=1;
inline int getid(char c){return c-'0';}
inline void add(int x){
    ++nod;e[nod].ln=e[lst].ln+1;
    int p=lst;lst=nod;
    while(p && !e[p].ch[x]){
        e[p].ch[x]=nod;
        p=e[p].link;
    }
    if(!p){
        e[nod].link=1;
        return;
    }
    int q=e[p].ch[x];
    if(e[q].ln==e[p].ln+1){
        e[nod].link=q;
        return;
    }
    int now=nod;
    int cln=++nod;
    e[cln]=e[q];e[cln].ln=e[p].ln+1;
    while(p && e[p].ch[x]==q){e[p].ch[x]=cln;p=e[p].link;}
    e[q].link=e[now].link=cln;
}
int val[20];
char c[Maxn];
int n;
inline int getnewln(int now,int x,int ln){
    while(now!=1 && !e[now].ch[x]) now=e[now].link,ln=e[now].ln;
    if(e[now].ch[x]) ++ln;return ln;
}
int lim[Maxn];
int A,B;
inline void init(){
    scanf("%s",c+1);n=strlen(c+1);
    int id=1,ln=0,now=1;
    fr(i,1,n){
        add(getid(c[i]));
        // cerr<<i<<endl;
        // cout<<i<<' '<<id<<' '<<getnewln(now,getid(c[id]),ln)<<' '<<id-i<<endl;
        while(id<=n && getnewln(now,getid(c[id]),ln)>=id-i){
            // cerr<<id<<endl;
            int x=getid(c[id]);
            while(now!=1 && !e[now].ch[x]) now=e[now].link,ln=e[now].ln;
            if(e[now].ch[x]) ++ln,now=e[now].ch[x];
            lim[id]=i;++id;
        }
    }
    fr(i,0,9) val[i]=read();A=read();B=read();
    // fr(i,1,n) cout<<i<<' '<<lim[i]<<endl;
}
int head,tail,stk[Maxn];
int f[Maxn];
inline void chkmin(int &x,int y){if(x>y) x=y;}
inline void work(){
    head=1,tail=0;
    fr(i,1,n){
        f[i]=f[i-1]+val[getid(c[i])];
        while(head<=tail && stk[head]<lim[i]) ++head;
        if(head<=tail) chkmin(f[i],f[stk[head]]+A*(i-stk[head])+B);
        while(head<=tail && f[i]-A*i<f[stk[tail]]-A*stk[tail]) --tail;
        stk[++tail]=i;
    }writeln(f[n]);
}
signed main(){
	// freopen("input.in","r",stdin);
	// freopen("output.out","w",stdout);
    init();work();
    // printf("\nTIME:%.3lf",(double)clock()/CLOCKS_PER_SEC);
	return 0;
}

詳細信息


Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 1ms
memory: 5904kb

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: 1ms
memory: 5624kb

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: 1ms
memory: 5628kb

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: 1ms
memory: 7692kb

input:

105317817326678173266278173266781861452966757817326678173266278886145296675781732667817326646678173266274192117326678173266784326678173266466781732662741921173271467739032664667817326627419211244018646678173266274192667817326627419211732667817326678432667817326646676064694317326627419211732667817326...

output:

1258663

result:

ok answer is '1258663'

Test #5:

score: 10
Accepted
time: 2ms
memory: 8420kb

input:

010101010101310101000101010101010101010101015194010101410101310101010101016101050901010101010101010101010101010121010101010301010101010101050101010131010401019101030101010101010106010101010101010301113101010101060101010101010221310101010101010101010201010101010101010101010101010201010101010101010301...

output:

634386

result:

ok answer is '634386'

Test #6:

score: 10
Accepted
time: 3ms
memory: 13180kb

input:

101101011011010110101101101011011010110101101101011010110110101101101011010110110101101101011010110110101101011011010110110101101011011010110101101101011011010110101101101011011010110101101101011010110110101101101011010110110101101101011010110110101101011011010110110101101011011010110101101101011011...

output:

3608448

result:

ok answer is '3608448'

Test #7:

score: 10
Accepted
time: 9ms
memory: 24116kb

input:

259056990780332590569987271259056990780332590569949056998727125905699078033259056998286994905632095600332590569982253590569907803325905699872712590569907803325905699490569987271259056990780332590569982869949056320956003325905699822589490569987271259056990780332590569982869949056320956003325905699822...

output:

46857468

result:

ok answer is '46857468'

Test #8:

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

input:

228255514297409372831124051231457518830714580983978118191715409980887870392763255958771396014724099273225818044544335318830714580983978118191715409980887870392763255958771396014724099273222875394216198066164777774453584645720613199953220643394961533112597700983978118191715409980887870392763255958771...

output:

38860522

result:

ok answer is '38860522'

Test #9:

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

input:

559026120443215529932053298946836947788255576080102636079256978346848066124067848713074979476892430650387372942634392777955392777605987788887027251714708216083863607925697834949925247190947471443668150708082380654358861507758294311830016300385819376425818027205596619887481716476691219729850438192848...

output:

34081603

result:

ok answer is '34081603'

Test #10:

score: 10
Accepted
time: 26ms
memory: 23596kb

input:

010101010101010101010101010101010101000101010101010101010101010101010101010101010103010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101015101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010601010101010101...

output:

3071979

result:

ok answer is '3071979'