Problem description

Resource constraints
Time limit: 1.0s memory limit: 256.0MB
Problem description
JiaoShou is about to go home after her trip in mainland China. In order to commemorate this trip, he decided to bring back some gifts to his good friends.
After walking out of the monster forest, JiaoShou saw N stones in a row.
These stones are very beautiful. JiaoShou decided to take them as a gift.
But the N stones were subjected to a special kind of magic.
If you want to remove stones, you must follow the following rules.
Continuous 2*K stones must be taken each time, and the weight sum of the first k stones shall be less than or equal to S, and the weight sum of the last K stones shall be less than or equal to S.
Due to time constraints, Jiaoshou can only take it once.
Now JiaoShou found the smart you and asked him how many stones he could take at most.
Input format
The first line contains two integers N, S.
The second line contains N integers, separated by spaces, representing the weight of each stone.
Output format
The first line outputs a number indicating the maximum number of stones that JiaoShou can take away.
Sample row input
　　8 3
　　1 1 1 1 1 1 1 1
Sample output
　　6
Sample interpretation
Select 6 consecutive 1s arbitrarily.
Data scale and agreement
For 20% data: n < = 1000
For 70% of data: n < = 100000
For 100% data: n < = 1000000, s < = 1012, the weight of each stone is less than or equal to 109 and non negative

Ideas

The idea is to use i and j to traverse in turn. i is the first pointer of k1 stones less than S, j is the first pointer of k2 stones less than S, and finally take the minimum values of k1 and k2
The code is as follows:

#include<iostream>
using namespace std;
int main()
{
	long long N, S, maxk = 0;
	cin >> N >> S;
	int* W = new int[N];
	for (int i = 0; i < N; i++)
	{
		cin >> W[i];
	}
	for (int i = 0; i < N; i++)
	{
		long long k1 = 0, k2 = 0;
		long long weight1 = 0, weight2 = 0;
		int j, k;
		for (j = i; j < N; j++)
		{
			weight1 += W[j];
			k1++;
			if (weight1 > S)
			{
				k1--;
				break;
			}
		}
		for (k = j; k < N; k++)
		{
			weight2 += W[k];
			k2++;
			if (weight2 > S)
			{
				k2--;
				break;
			}
		}
		maxk = max(max(k1, k2) / 2, maxk);
		maxk = max(min(k1, k2), maxk);
	}
	cout << 2 * maxk << endl;
	return 0;
}

The above code can only get 20 points. Obviously, the examples in 2 and 3 can't pass and will timeout, so we can only find ways to improve. It's easy to think that it takes time to traverse and obtain the sum value every time, and it's obvious that there is a repetition with the previous one, we can open an array to prefix and sum.
And changed his mind. Instead of traversal, he used binary search to find the interval in line with S. sure enough, the problem suddenly opened up
Dichotomy is generally applicable to the value found in an interval

Code improvement

Here, the array starts from 1 to facilitate the calculation of the first sum of mid, because the initialization initializes Sum[0] to 0
Then the sum of the first mid numbers (including i) can be directly expressed as
Sum[i]-Sum[i-mid]
The sum of the number of mid after i can be expressed as
S[mid+i]-S[i]

#include<iostream>
#include<string.h>
using namespace std;
int check(long long mid,long long N,long long S,long long *Sum)
{
	for (int i = mid; i <= N - mid; i++)
	{
		if (Sum[i] - Sum[i - mid] <= S && Sum[i + mid] - Sum[i] <= S)
		{
			return 1;
		}
	}
	return 0;
}
int main()
{
	long long N, S;
	cin >> N >> S;
	long long* W = new long long[N+1];
	long long* Sum = new long long[N+1];//Prefix and
	memset(W, 0, sizeof(W));
	memset(Sum, 0, sizeof(Sum));
	for (int i = 1; i <= N; i++)
	{
		cin >> W[i];
		Sum[i] = Sum[i - 1] + W[i];
			
	}
	long long l = 1, r = N;
	while (l < r)
	{
		long long mid = (l + r + 1) >> 1;
		if (check(mid, N, S, Sum))
		{
			l = mid;
		}
		else
		{
			r = mid - 1;
		}
	}
	cout << 2 * l << endl;
	return 0;
}
/*
8 3
1 1 1 1 1 1 1 1

8 3
1 2 3 4 5 6 7 8

*/

This question really bothers me for a long time.... Maybe I'm too good