QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#217100#6366. MessageUstinian26WA 11ms19248kbC++141.8kb2023-10-16 14:53:342023-10-16 14:53:36

Judging History

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

  • [2023-10-16 14:53:36]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:19248kb
  • [2023-10-16 14:53:34]
  • 提交

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'