QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#601131 | #562. 码农 | strlen_s_ | 100 ✓ | 47ms | 43004kb | C++17 | 2.2kb | 2024-09-29 20:59:23 | 2024-09-29 20:59:23 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define mid (l+r>>1)
#define ls (k<<1)
#define rs (k<<1|1)
using namespace std;
const int N=1e5+10,M=2e5+10;
const ll inf=1e18;
struct node{
int ch[10],len,fa;
}t[M];
int top=1,lst=1;
int f[M][18];
int mp[M],pl[N];
vector<int>G[M];
char c[N];
int v[10],tc,tp;
int n;
ll dp[N];
struct segtree{
ll mi[N<<2],lz[N<<2];
void init(){for(int i=1;i<=n*4;i++)mi[i]=inf;}
void pushup(int k){mi[k]=min(mi[ls],mi[rs]);}
void ch(int k,ll z){mi[k]+=z,lz[k]+=z;}
void pushdown(int k){
if(!lz[k])return;
ch(ls,lz[k]),ch(rs,lz[k]),lz[k]=0;
}
void upd(int k,int l,int r,int x,ll z){
if(l==r){mi[k]=z;return;}
pushdown(k);
if(mid>=x)upd(ls,l,mid,x,z);
else upd(rs,mid+1,r,x,z);
pushup(k);
}
ll qry(int k,int l,int r,int x,int y){
if(x<=l&&r<=y)return mi[k];
pushdown(k);
ll ans=inf;
if(mid>=x)ans=min(ans,qry(ls,l,mid,x,y));
if(y>mid)ans=min(ans,qry(rs,mid+1,r,x,y));
return ans;
}
}T;
int clone(int k){t[++top]=t[k];return top;}
void insert(int x,int id){
int cur=++top,p=lst;lst=cur;t[cur].len=t[p].len+1;mp[cur]=id,pl[id]=cur;
while(!t[p].ch[x]&&p)t[p].ch[x]=cur,p=t[p].fa;
if(!p){t[cur].fa=1;return;}
int q=t[p].ch[x];
if(t[q].len==t[p].len+1){t[cur].fa=q;return;}
int c=clone(q);t[c].len=t[p].len+1,t[q].fa=t[cur].fa=c;
while(t[p].ch[x]==q&&p)t[p].ch[x]=c,p=t[p].fa;
}
void dfs(int u){for(auto v:G[u])dfs(v),mp[u]=min(mp[u],mp[v]);}
ll qry(int p){
int x=pl[p];
for(int i=17;i>=0;i--)if(f[x][i]&&p-mp[f[x][i]]<t[t[f[x][i]].fa].len+1)x=f[x][i];
x=f[x][0];if(x==1)return inf;
int len=min(t[x].len,p-mp[x]);
return T.qry(1,1,n,p-len+1,p)+tp;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>(c+1);n=strlen(c+1);memset(mp,0x3f,sizeof(mp));
for(int i=1;i<=n;i++)insert(c[i]-'0',i);t[0].len=-1,mp[0]=0;
for(int i=2;i<=top;i++)f[i][0]=t[i].fa,G[t[i].fa].push_back(i);
dfs(1);for(int j=1;j<=17;j++)for(int i=1;i<=top;i++)f[i][j]=f[f[i][j-1]][j-1];
for(int i=0;i<10;i++)cin>>v[i];cin>>tc>>tp;T.init();
for(int i=1;i<=n;i++){
T.ch(1,tc);
dp[i]=min(dp[i-1]+v[c[i]-'0'],qry(i));
if(i<n)T.upd(1,1,n,i+1,dp[i]);
}
cout<<dp[n]<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 0ms
memory: 13892kb
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: 2ms
memory: 13876kb
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: 13908kb
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: 3ms
memory: 16264kb
input:
105317817326678173266278173266781861452966757817326678173266278886145296675781732667817326646678173266274192117326678173266784326678173266466781732662741921173271467739032664667817326627419211244018646678173266274192667817326627419211732667817326678432667817326646676064694317326627419211732667817326...
output:
1258663
result:
ok answer is '1258663'
Test #5:
score: 10
Accepted
time: 6ms
memory: 19412kb
input:
010101010101310101000101010101010101010101015194010101410101310101010101016101050901010101010101010101010101010121010101010301010101010101050101010131010401019101030101010101010106010101010101010301113101010101060101010101010221310101010101010101010201010101010101010101010101010201010101010101010301...
output:
634386
result:
ok answer is '634386'
Test #6:
score: 10
Accepted
time: 31ms
memory: 26824kb
input:
101101011011010110101101101011011010110101101101011010110110101101101011010110110101101101011010110110101101011011010110110101101011011010110101101101011011010110101101101011011010110101101101011010110110101101101011010110110101101101011010110110101101011011010110110101101011011010110101101101011011...
output:
3608448
result:
ok answer is '3608448'
Test #7:
score: 10
Accepted
time: 47ms
memory: 41596kb
input:
259056990780332590569987271259056990780332590569949056998727125905699078033259056998286994905632095600332590569982253590569907803325905699872712590569907803325905699490569987271259056990780332590569982869949056320956003325905699822589490569987271259056990780332590569982869949056320956003325905699822...
output:
46857468
result:
ok answer is '46857468'
Test #8:
score: 10
Accepted
time: 43ms
memory: 43004kb
input:
228255514297409372831124051231457518830714580983978118191715409980887870392763255958771396014724099273225818044544335318830714580983978118191715409980887870392763255958771396014724099273222875394216198066164777774453584645720613199953220643394961533112597700983978118191715409980887870392763255958771...
output:
38860522
result:
ok answer is '38860522'
Test #9:
score: 10
Accepted
time: 45ms
memory: 41992kb
input:
559026120443215529932053298946836947788255576080102636079256978346848066124067848713074979476892430650387372942634392777955392777605987788887027251714708216083863607925697834949925247190947471443668150708082380654358861507758294311830016300385819376425818027205596619887481716476691219729850438192848...
output:
34081603
result:
ok answer is '34081603'
Test #10:
score: 10
Accepted
time: 47ms
memory: 41912kb
input:
010101010101010101010101010101010101000101010101010101010101010101010101010101010103010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101015101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010601010101010101...
output:
3071979
result:
ok answer is '3071979'