QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#217100 | #6366. Message | Ustinian26 | WA | 11ms | 19248kb | C++14 | 1.8kb | 2023-10-16 14:53:34 | 2023-10-16 14:53:36 |
Judging History
answer
#include<bits/stdc++.h>
#define iI inline int
#define iV inline void
#define iB inline bool
#define eb emplace_back
#define ll long long
#define FOR(i,s,t) for(int i=(s);i<=(t);++i)
#define ROF(i,s,t) for(int i=(s);i>=(t);--i)
using namespace std;
iI read() {
int x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+(c^48),c=getchar();
return x;
}
const int N=2e5+3;
const ll inf=1e18;
int sid,T,n,m,w[N];
bool suc[N][26],pre[N][26];
ll f[N],g[N];
char s[N],t[N];
iV chn(ll &x,ll y) {x=x<y?x:y;}
iV solA() {
if(n<m) return void(printf("You better start from scratch man...\n"));
FOR(i,1,n) g[i]=g[i-1]+w[i];
ll res=inf;
FOR(i,1,n-m) chn(res,g[i]+g[n]-g[i+m]);
printf("%lld\n",res);
}
iB chk() {
FOR(i,2,n) if(s[i]!=s[i-1]) return false;
return true;
}
int cnt,mat[N],cur,tmp[N];
iV sol() {
scanf("%s%s",s+1,t+1);
n=strlen(s+1),m=strlen(t+1);
FOR(i,1,n) w[i]=read();
if(chk()) return solA();
FOR(i,1,m) pre[i][t[i]-'a']=suc[i][t[i]-'a']=1;
FOR(i,1,m) FOR(j,0,25) pre[i][j]|=pre[i-1][j];
ROF(i,m,1) FOR(j,0,25) suc[i][j]|=suc[i+1][j];
FOR(i,1,m) f[i]=inf;f[0]=0;
mat[cnt=1]=0;
FOR(i,1,n) {
int c=s[i]-'a';
ROF(j,cnt,1) {
int k=mat[j];
if(s[i]==t[k+1]&&f[k]<f[k+1]) {
if(f[k+1]==inf) tmp[++cur]=k+1;
f[k+1]=f[k];
}
if(pre[k][c]&&suc[k+1][c]) {f[k]=inf;continue;}
f[k]+=w[i],tmp[++cur]=k;
}
FOR(j,1,cur) mat[j]=tmp[cur-j+1];
cnt=cur,cur=0;
}
if(f[m]<inf) printf("%lld\n",f[m]);
else printf("You better start from scratch man...\n");
FOR(i,1,m) memset(pre[i],0,26),memset(suc[i],0,26);
}
int main() {
sol();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 12012kb
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: 10016kb
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: 11ms
memory: 19248kb
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: 8ms
memory: 19084kb
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: 8ms
memory: 18888kb
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: 11ms
memory: 18412kb
input:
bbaaaabbbbbabaababbaaabbbabaaaababaababaabababbbbabbbbababaabaaabbabaaaabbbabbaababababbabbbabbaababaaaaaabbabbbababbaabbbabbbabbbabaababaaaaaabaaababbbbbbaabaabaaaaaaabbbaaabaabbbababbbbbabbababaababaabbababbaababbbbbbbbbbbaabbbbbabaaabaabaaabaaaaabaaaabbbbbbbaaaabaabbbababbaaaabbabababbbabbbbabbab...
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 9ms
memory: 18416kb
input:
hdhlkjabgckjkagfgkigfebfjmdabahajicgkfmblafmfgkiimkjlciiaegbkbkicgklhbhfmclghkleghmckbjliiicmmecldieghfdeghgechcjahdfebkhdigbkklcclieccijaemchbmfcggcjmgbdjhcbacleajjjledkfdjebgdmgahkjigjjighlbedbellabffeeckfbghcblmmgjijdehmcameeledejfijfmfcfkjdjklfldhmkabblcbgebhibkmihelehjccgggjhhbjehfidfmmjdgmmjbf...
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 8ms
memory: 18664kb
input:
soibsuydrizsuvymezuyrewmgwpnzxgyggpzjkdzooisgzbkfqjzkfcklluotqpwganvksoqtzixkfkrtqobdnregwgkxjwzsruvhztscxjyqlhfytomzhxiglxemdhkjnskrsqngojffogrkbygmdgzfwrlhwhhngqpjpepqgynsdybhpuaqhgjroijqofiwnxgxdmhofwsjnmwitruiesefzmabcfsyzrrruidewjowfkwwwqhztsmmtdnejlqhkmbpmknlxijnmzbtqviburbqwufipqsrqplcelovsxz...
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
aaaaaaaaaa a 670064684 12247274 885150692 755303894 373857482 772871474 451986656 733926307 275101324 732261937
output:
4777621032
result:
ok single line: '4777621032'
Test #10:
score: -100
Wrong Answer
time: 1ms
memory: 8008kb
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:
5290902883
result:
wrong answer 1st lines differ - expected: '5115514604', found: '5290902883'