QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#590761 | #562. 码农 | Crying | 100 ✓ | 50ms | 16352kb | C++14 | 3.2kb | 2024-09-26 11:07:06 | 2024-09-26 11:07:06 |
Judging History
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'