There are n water bottles with infinite capacity, numbered from 1 to n. Initially, number i was filled with A_ I unit of water
You can perform no more than k operations, each time selecting a number x that meets the requirements of 1<=x<=n-1, and then pouring all the water from the x kettle into the x+1 kettle.
Finally, you can choose exactly one kettle and drink all the water from it. Now, please find out the maximum number of units of water you can drink.
Question input:
The first line is a positive integer n, which represents the number of water bottles.
The second line is a non negative integer k, which represents the maximum number of operations.
The third line contains n non negative integers, with adjacent numbers separated by spaces, indicating the initial water capacity A of the kettle_ 1, A_ 2 A_ N.
Question output:
A row containing only one non negative integer representing the answer.
Sample input:
10 5
890 965 256 419 296 987 45 676 976 742
Sample output:
3813
Data range:
For 10% of the data, ensure that n<=10.
For 30% of the data, ensure that n<=100.
For 50% of the data, ensure n<=1000.
For 70% of the data, ensure that n<=1e5.
For 100% data, ensure that 1<=n<=1e6,0<=k<=n-1,0<=A_ I<=1e3
ACcode:
#include<bits/stdc++.h>
using namespace std;
char s[100010];
char t[100010];
char w[100010];
long long n,k,a[1000010],ret;
int main()
{
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
a[i]=a[i-1]+x;
}
k++;
for(int i=1;i+k-1<=n;i++)
{
int u=i+k-1;
ret=max(ret,a[u]-a[i-1]);
}
cout<<ret;
return 0;
return 0;
}
train of thought：https://www.xinyoudui.com/courses/572#/pages/14670
page：9
有n个容量无穷大的水壶，它们从1~n编号，初始时i号水壶中装有A_i单位的水.
你可以进行不超过k次操作，每次操作需要选择一个满足1<=x<=n-1的编号x，然后把x号水壶中的水全部倒入x+1号水壶中。
最后你可以任意选择恰好一个水壶，并喝掉水壶中所有的水。现在请你求出，你最多能喝到多少单位的水。
题目输入：
第一行一个正整数n，表示水壶的个数。
第二行一个非负整数k，表示操作次数上限。
第三行n个非负整数，相邻两个数用空格隔开，表示水壶的初始装水量A_1,A_2,…A_n。
题目输出：
一行，仅一个非负整数，表示答案。
样例输入：
10 5 890 965 256 419 296 987 45 676 976 742
样例输出：
3813
数据范围:
对于10%的数据，保证n<=10。
对于30%的数据，保证n<=100。
对于50%的数据，保证n<=1000。
对于70%的数据，保证n<=1e5。
对于100%的数据，保证1<=n<=1e6,0<=k<=n-1,0<=A_i<=1e3