QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#699990#5981. Costly Binary Searchmasterhuang8 67ms235244kbC++23816b2024-11-02 11:30:242024-11-02 11:30:24

Judging History

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

  • [2024-11-02 11:30:24]
  • 评测
  • 测评结果:8
  • 用时:67ms
  • 内存:235244kb
  • [2024-11-02 11:30:24]
  • 提交

answer

#include<bits/stdc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=1e6+5;
int T,n,a[N],L[180][N],R[180][N];
string C;
inline void sol()
{
	for(int i=0;i<(n=C.size());i++) a[i+1]=C[i]-'0';
	for(int s=0;;s++)
	{
		for(int i=0;i<=n+1;i++) L[s][i]=i+1,R[s][i]=i-1;
		for(int i=1;i<=n;i++) if(s>=a[i])
		{
			int l=L[s-a[i]][i-1],r=R[s-a[i]][i+1];
			L[s][r]=min(L[s][r],l);
			R[s][l]=max(R[s][l],r);
		}
		for(int i=2;i<=n;i++) R[s][i]=max(R[s][i],R[s][i-1]);
		for(int i=n-1;i;i--) L[s][i]=min(L[s][i],L[s][i+1]);
		if(R[s][1]>=n) return cout<<s<<"\n",void();
	}
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;
	for(int i=1;i<=T;i++) cin>>C,cout<<"Case #"<<i<<": ",sol();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 8
Accepted

Test #1:

score: 8
Accepted
time: 67ms
memory: 235244kb

input:

50
8
5128831164925953487661279378526736416489768154389124821528467927357884749642747626797857463132866343496157991453139582295398452863172464853698678624523849653538713928372648295734165346972222781179687541337591976277864785653638476127839556323849395641196246971351933655287441377531627938395427487...

output:

Case #1: 8
Case #2: 37
Case #3: 34
Case #4: 37
Case #5: 34
Case #6: 114
Case #7: 126
Case #8: 24
Case #9: 37
Case #10: 103
Case #11: 36
Case #12: 64
Case #13: 37
Case #14: 117
Case #15: 37
Case #16: 35
Case #17: 14
Case #18: 34
Case #19: 36
Case #20: 37
Case #21: 38
Case #22: 39
Case #23: 14
Case #2...

result:

ok 50 lines

Subtask #2:

score: 0
Memory Limit Exceeded

Test #2:

score: 0
Memory Limit Exceeded

input:

50
647322722753778843259213887674615134214258235986992692879314555957455541351526284343217116351733247781713552149464672262787737941588358671583528664757823365936975517145283412965139791726299864122725212222496898855627124979178341548651669956711341742838725446489235961853391195148929571712449139335...

output:

Case #1: 42
Case #2: 43
Case #3: 120
Case #4: 42
Case #5: 43
Case #6: 43
Case #7: 31
Case #8: 43
Case #9: 171
Case #10: 42
Case #11: 39
Case #12: 42
Case #13: 42
Case #14: 44
Case #15: 39
Case #16: 20
Case #17: 180
Case #18: 30
Case #19: 45
Case #20: 43
Case #21: 44
Case #22: 31
Case #23: 83
Case #2...

result: