## 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