QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#592996 | #562. 码农 | xlwang | 100 ✓ | 26ms | 24932kb | C++14 | 3.0kb | 2024-09-27 10:59:55 | 2024-09-27 10:59:56 |
Judging History
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'