QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#640944#6366. MessagelgvcTL 432ms6700kbC++231.0kb2024-10-14 17:04:332024-10-14 17:04:38

Judging History

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

  • [2024-10-14 17:04:38]
  • 评测
  • 测评结果:TL
  • 用时:432ms
  • 内存:6700kb
  • [2024-10-14 17:04:33]
  • 提交

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

result: