QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#332209 | #6366. Message | xcyyyyy | WA | 164ms | 98928kb | C++14 | 2.3kb | 2024-02-19 11:57:07 | 2024-02-19 11:57:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 200005
int n,m,c[N];
char s[N],t[N];
int num;
int vis[200];
pair<int,int> x[60];char a[60];
int v[60][26],b[60][26];
ll f[N][60];int cnt[60];
vector<int> G;
int main(){
srand(time(0));
scanf("%s%s",s+1,t+1);n=strlen(s+1),m=strlen(t+1);
for(int i=1;i<=n;i++)scanf("%d",&c[i]);
memset(vis,0,sizeof(vis));
for(int i=1;i<=m;i++)if(!vis[t[i]])vis[t[i]]=1,x[++num]={i,t[i]};
memset(vis,0,sizeof(vis));
for(int i=m;i;i--)if(!vis[t[i]])vis[t[i]]=1,x[++num]={i,t[i]};
sort(x+1,x+1+num);num=unique(x+1,x+1+num)-x-1;
x[num+1].first=m+1;
for(int i=1;i<=num;i++){
a[i]=x[i].second;
for(int j=x[i].first+1;j<x[i+1].first;j++)
++v[i][t[j]-'a'];
for(int j=0;j<26;j++){
bool f=false,g=false;
for(int k=1;k<=i;k++)f|=x[k].second==j+'a';
for(int k=i+1;k<=num;k++)g|=x[k].second==j+'a';
if(!f||!g)v[i][j]=n+1;
}
}
memset(f,-0x3f,sizeof(f));
for(int i=0;i<=n;i++)f[i][0]=0;
for(int j=1;j<=num;j++){//转移第 j 段
memset(cnt,0,sizeof(cnt));int gd=0,all=0;ll w=0;
for(int i=0;i<26;i++)gd+=v[j][i]==0,all+=v[j][i]!=n+1;
for(int i=0,r=0;i<n;i++){//printf("Case %d \n",i);
gd-=v[j][s[i+1]-'a']!=n+1&&cnt[s[i+1]-'a']==v[j][s[i+1]-'a'];
--cnt[s[i+1]-'a'];
w-=(v[j][s[i+1]-'a']!=n+1)*c[i+1];
//printf("del %d %c | ",i+1,s[i+1]);
//puts("");
while(r<n&&(gd!=all&&cnt[s[r+1]-'a']+1<=v[j][s[r+1]-'a']||r<i+1)){
++r;
++cnt[s[r]-'a'];
//printf("add %d %c | ",r,s[r]);
w+=(v[j][s[r]-'a']!=n+1)*c[r];
gd+=v[j][s[r]-'a']!=n+1&&cnt[s[r]-'a']==v[j][s[r]-'a'];
}//puts("");
//printf("%d %d %d\n",gd,all,r);
//for(int i=0;i<26;i++)cout<<cnt[i]<<" ";puts("");
if(s[i+1]==a[j]&&gd==all)f[r][j]=max(f[i][j-1]+w+c[i+1],f[r][j]);
}
for(int i=1;i<=n;i++)if(v[j][s[i]-'a']==n+1)f[i][j]=max(f[i][j],f[i-1][j]);
}
if(f[n][num]<0)return puts("You better start from scratch man..."),0;
f[n][num]=-f[n][num];
for(int i=1;i<=n;i++)f[n][num]+=c[i];
printf("%lld\n",f[n][num]);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 98224kb
input:
ababccb abc 7 2 2 4 3 2 1
output:
7
result:
ok single line: '7'
Test #2:
score: 0
Accepted
time: 7ms
memory: 98068kb
input:
babab baab 2 1 3 2 4
output:
You better start from scratch man...
result:
ok single line: 'You better start from scratch man...'
Test #3:
score: 0
Accepted
time: 32ms
memory: 98796kb
input:
bbaaaabbbbbabaababbaaabbbabaaaababaababaabababbbbabbbbababaabaaabbabaaaabbbabbaababababbabbbabbaababaaaaaabbabbbababbaabbbabbbabbbabaababaaaaaabaaababbbbbbaabaabaaaaaaabbbaaabaabbbababbbbbabbababaababaabbababbaababbbbbbbbbbbaabbbbbabaaabaabaaabaaaaabaaaabbbbbbbaaaabaabbbababbaaaabbabababbbabbbbabbab...
output:
You better start from scratch man...
result:
ok single line: 'You better start from scratch man...'
Test #4:
score: 0
Accepted
time: 61ms
memory: 98672kb
input:
bdabcfbdfcffebebcabbadacbbaeeaffbdedeedfabefdfdbddcecdaaddafdfbbdceccedebcecdfbcfbaafcefeecffdabfaacbeeecfeffaaafaefdcdaaeaeecfafcdadbfbccbdecacfeabdbfcacafebdcfbfbebacbffaecbfbcedccabbdecabaebbbdbcfbaeadfcadfadfaebaddbebfcbefdabdcefbbdaaaabcefedabcabcafedcfadedfdcbbccbffdcfdfcfcdfcfbbdabdbbeecafecc...
output:
You better start from scratch man...
result:
ok single line: 'You better start from scratch man...'
Test #5:
score: 0
Accepted
time: 163ms
memory: 98680kb
input:
soibsuydrizsuvymezuyrewmgwpnzxgyggpzjkdzooisgzbkfqjzkfcklluotqpwganvksoqtzixkfkrtqobdnregwgkxjwzsruvhztscxjyqlhfytomzhxiglxemdhkjnskrsqngojffogrkbygmdgzfwrlhwhhngqpjpepqgynsdybhpuaqhgjroijqofiwnxgxdmhofwsjnmwitruiesefzmabcfsyzrrruidewjowfkwwwqhztsmmtdnejlqhkmbpmknlxijnmzbtqviburbqwufipqsrqplcelovsxz...
output:
You better start from scratch man...
result:
ok single line: 'You better start from scratch man...'
Test #6:
score: 0
Accepted
time: 34ms
memory: 98852kb
input:
bbaaaabbbbbabaababbaaabbbabaaaababaababaabababbbbabbbbababaabaaabbabaaaabbbabbaababababbabbbabbaababaaaaaabbabbbababbaabbbabbbabbbabaababaaaaaabaaababbbbbbaabaabaaaaaaabbbaaabaabbbababbbbbabbababaababaabbababbaababbbbbbbbbbbaabbbbbabaaabaabaaabaaaaabaaaabbbbbbbaaaabaabbbababbaaaabbabababbbabbbbabbab...
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 93ms
memory: 98924kb
input:
hdhlkjabgckjkagfgkigfebfjmdabahajicgkfmblafmfgkiimkjlciiaegbkbkicgklhbhfmclghkleghmckbjliiicmmecldieghfdeghgechcjahdfebkhdigbkklcclieccijaemchbmfcggcjmgbdjhcbacleajjjledkfdjebgdmgahkjigjjighlbedbellabffeeckfbghcblmmgjijdehmcameeledejfijfmfcfkjdjklfldhmkabblcbgebhibkmihelehjccgggjhhbjehfidfmmjdgmmjbf...
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 164ms
memory: 98860kb
input:
soibsuydrizsuvymezuyrewmgwpnzxgyggpzjkdzooisgzbkfqjzkfcklluotqpwganvksoqtzixkfkrtqobdnregwgkxjwzsruvhztscxjyqlhfytomzhxiglxemdhkjnskrsqngojffogrkbygmdgzfwrlhwhhngqpjpepqgynsdybhpuaqhgjroijqofiwnxgxdmhofwsjnmwitruiesefzmabcfsyzrrruidewjowfkwwwqhztsmmtdnejlqhkmbpmknlxijnmzbtqviburbqwufipqsrqplcelovsxz...
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 0ms
memory: 97984kb
input:
aaaaaaaaaa a 670064684 12247274 885150692 755303894 373857482 772871474 451986656 733926307 275101324 732261937
output:
4777621032
result:
ok single line: '4777621032'
Test #10:
score: 0
Accepted
time: 4ms
memory: 98804kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaa 807194254 763061330 636628022 447638039 310117480 873320507 134259988 666480259 747042520 231541618 643931761 30317274 158530414 253502390 229547045 438239031 709645547 367432988 755781758 67144518 360508870 862615691 635226301 863755466 104979114 4...
output:
5115514604
result:
ok single line: '5115514604'
Test #11:
score: 0
Accepted
time: 4ms
memory: 98484kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaa 768295104 305748099 281563038 518303412 678146171 512832379 509999474 360793781 979858190 884904151 886121576 776530718 147119220 985829130 553994391 500082956 167860347 562080893 520228135 790526162 270707017 179265550 913606870 245853815 83...
output:
21140461276
result:
ok single line: '21140461276'
Test #12:
score: 0
Accepted
time: 10ms
memory: 97716kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 684483834 637018127 270602950 736485564 883414052 758886073 266638494 906099301 851227039 479339928 603217972 474167559 537788182 324629484 719852776 8079...
output:
27302362948
result:
ok single line: '27302362948'
Test #13:
score: 0
Accepted
time: 0ms
memory: 97932kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
131859070652
result:
ok single line: '131859070652'
Test #14:
score: 0
Accepted
time: 0ms
memory: 97732kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
781196173176
result:
ok single line: '781196173176'
Test #15:
score: 0
Accepted
time: 3ms
memory: 97736kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
4343956108320
result:
ok single line: '4343956108320'
Test #16:
score: 0
Accepted
time: 8ms
memory: 98520kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
18494567762260
result:
ok single line: '18494567762260'
Test #17:
score: 0
Accepted
time: 12ms
memory: 98556kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
32209183658799
result:
ok single line: '32209183658799'
Test #18:
score: 0
Accepted
time: 23ms
memory: 98572kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
54681136007004
result:
ok single line: '54681136007004'
Test #19:
score: 0
Accepted
time: 23ms
memory: 98928kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
29370598770431
result:
ok single line: '29370598770431'
Test #20:
score: 0
Accepted
time: 3ms
memory: 97704kb
input:
aaaabababb bb 476848657 19478030 860633182 479517749 926931997 990353030 811177212 276072809 44418816 639422667
output:
3786744940
result:
ok single line: '3786744940'
Test #21:
score: 0
Accepted
time: 0ms
memory: 97700kb
input:
baabbbaabbbbbbaaabbabababbbabb aabbbbbbbbbbbb 596942736 513321407 582182914 466363879 661702687 696876564 738552457 374802663 475543850 315580035 306727219 980454952 485808481 677883937 518967937 895712736 991586358 554417767 795851770 921017576 109301858 423859119 202619045 804565823 583428190 4070...
output:
9486081373
result:
ok single line: '9486081373'
Test #22:
score: 0
Accepted
time: 3ms
memory: 97772kb
input:
bbaaaaababbaabbbabaaaaaaaaaaaaaaabaabaabbabbbbaaaa bba 517088091 307183015 994179974 164146474 156595248 11692792 656694126 683962150 307132163 246359231 966105863 281059597 304728259 612665622 916423647 405320553 230841790 746930714 950416681 343242506 418374186 670629995 146835514 191417218 469803...
output:
21735754192
result:
ok single line: '21735754192'
Test #23:
score: 0
Accepted
time: 0ms
memory: 98684kb
input:
abbbbabbbbbaaaabaabbbaaabaababaaababaababbbaaaabbaabbbabbaabbaabbbbbabbbbaabaabaabbbaabbaaaabaaabbab bbbbbbbbbbbbab 224008866 420036954 610760159 229448373 88014692 800505315 190642695 680916401 526205898 463834969 506379052 591268851 942360508 176667947 891525614 324651315 294533169 355712507 94407...
output:
40969461750
result:
ok single line: '40969461750'
Test #24:
score: -100
Wrong Answer
time: 7ms
memory: 98420kb
input:
baabaaabaabbbbabaaaabaaabaabbababbaaababbbaababbbaabbbababaaababbbaabbbabaaabbbabaabbaaabaaaaabaaabaaabaaaababbbbbbbabbabaabbbabababbbbbaaaaaaabbbbbbbbaababaababbbbbbaaaaaabbabbbabbbababababaaaaabbaaababbabbbbaaabbbaabaabaabaaabaabbbaaaaaabbaaaabbbbbbaabbabaabbbabbaaabababbbabaabbbbbabbbbbbababbbaab...
output:
157241082176
result:
wrong answer 1st lines differ - expected: '158990471979', found: '157241082176'