QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#601131#562. 码农strlen_s_100 ✓47ms43004kbC++172.2kb2024-09-29 20:59:232024-09-29 20:59:23

Judging History

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

  • [2024-09-29 20:59:23]
  • 评测
  • 测评结果:100
  • 用时:47ms
  • 内存:43004kb
  • [2024-09-29 20:59:23]
  • 提交

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'