QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#640944 | #6366. Message | lgvc | TL | 432ms | 6700kb | C++23 | 1.0kb | 2024-10-14 17:04:33 | 2024-10-14 17:04:38 |
Judging History
answer
#include <bits/stdc++.h>
#define INF_LL (0x3f3f3f3f3f3f3f3f)
char s[200009],t[200009];
int N,M,v1[30],v2[30],a[200009];
long long su,dp[200009];
signed main(void) {
scanf("%s",s+1);
scanf("%s",t+1);
N=strlen(s+1);M=strlen(t+1);
for(int i=1;i<=M;i++) v1[t[i]-'a']++;
memset(dp,-0x3f,sizeof(dp));
for(int i=1;i<=N;i++) scanf("%d",&a[i]),su+=a[i];
for(int i=1;i<=N;i++) {
if(s[i]==t[1]) {
dp[i]=a[i];
}
}
int id=1;
for(int i=1;i<M;i++) {
v1[t[i]-'a']--;
v2[t[i]-'a']++;
int as=0;
for(int j=0;j<26;j++) {
if(v1[j]&&v2[j]) as|=(1<<j);
}
long long ma=-INF_LL;
while(dp[id]<0&&id<=N) id++;
#pragma GCC unroll 50
for(int j=id;j<=N-(M-i)+1;j++) {
long long tq=ma+a[j];
if((as>>s[j]-'a')&1) ma=-INF_LL;
ma=std::max(ma,dp[j]);
if(t[i+1]==s[j]) dp[j]=tq;else dp[j]=-INF_LL;
}
}
long long as=-INF_LL;
for(int i=M;i<=N;i++) as=std::max(as,dp[i]);
if(as<0) {
printf("You better start from scratch man...");
} else {
printf("%lld",su-as);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5408kb
input:
ababccb abc 7 2 2 4 3 2 1
output:
7
result:
ok single line: '7'
Test #2:
score: 0
Accepted
time: 0ms
memory: 5468kb
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: 21ms
memory: 6640kb
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: 16ms
memory: 6516kb
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: 21ms
memory: 6572kb
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: 13ms
memory: 6700kb
input:
bbaaaabbbbbabaababbaaabbbabaaaababaababaabababbbbabbbbababaabaaabbabaaaabbbabbaababababbabbbabbaababaaaaaabbabbbababbaabbbabbbabbbabaababaaaaaabaaababbbbbbaabaabaaaaaaabbbaaabaabbbababbbbbabbababaababaabbababbaababbbbbbbbbbbaabbbbbabaaabaabaaabaaaaabaaaabbbbbbbaaaabaabbbababbaaaabbabababbbabbbbabbab...
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 15ms
memory: 6512kb
input:
hdhlkjabgckjkagfgkigfebfjmdabahajicgkfmblafmfgkiimkjlciiaegbkbkicgklhbhfmclghkleghmckbjliiicmmecldieghfdeghgechcjahdfebkhdigbkklcclieccijaemchbmfcggcjmgbdjhcbacleajjjledkfdjebgdmgahkjigjjighlbedbellabffeeckfbghcblmmgjijdehmcameeledejfijfmfcfkjdjklfldhmkabblcbgebhibkmihelehjccgggjhhbjehfidfmmjdgmmjbf...
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 20ms
memory: 6640kb
input:
soibsuydrizsuvymezuyrewmgwpnzxgyggpzjkdzooisgzbkfqjzkfcklluotqpwganvksoqtzixkfkrtqobdnregwgkxjwzsruvhztscxjyqlhfytomzhxiglxemdhkjnskrsqngojffogrkbygmdgzfwrlhwhhngqpjpepqgynsdybhpuaqhgjroijqofiwnxgxdmhofwsjnmwitruiesefzmabcfsyzrrruidewjowfkwwwqhztsmmtdnejlqhkmbpmknlxijnmzbtqviburbqwufipqsrqplcelovsxz...
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 1ms
memory: 6380kb
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: 1ms
memory: 5348kb
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: 1ms
memory: 5532kb
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: 1ms
memory: 5424kb
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: 1ms
memory: 5548kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
131859070652
result:
ok single line: '131859070652'
Test #14:
score: 0
Accepted
time: 3ms
memory: 5500kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
781196173176
result:
ok single line: '781196173176'
Test #15:
score: 0
Accepted
time: 12ms
memory: 5404kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
4343956108320
result:
ok single line: '4343956108320'
Test #16:
score: 0
Accepted
time: 432ms
memory: 5616kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
18494567762260
result:
ok single line: '18494567762260'
Test #17:
score: -100
Time Limit Exceeded
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
32209183658799