bunbohue's blog

By bunbohue, history, 2 months ago, In English

Hello Codeforces,

My sister implemented the solution for 279B — Books here:

https://ideone.com/uPow6L

And so amazing !!!! This solution is accepted. I've tried but cannot create the test case to prove this solution is wrong. Can you help me ? Or can you prove that this solution is correct

Thank you a lot for your help.

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

That solution is correct. It's a basic implementation of two-pointers.

At any time, if sum <= m, then [l, i] is a valid answer. From [l, i — 1], we should increase the length by one. Otherwise, we keep the current length at the same amount, from [l, i — 1] to [l + 1, i]

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Two-pointers obviously,the solution is correct. Please tell her to speak C++ the next time(if she can) like this,because I know little about Python:

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,l=1,r,a[100005];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		a[i]+=a[i-1];
	}
	for(r=1;r<=n;r++)
	{
		while(a[r]-a[l-1]>m) l++;
		if(r-l+1>ans) ans=r-l+1;
	}
	cout<<ans;
	return 0;
}