# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1138116 | MattNattFeczan | Rice Hub (IOI11_ricehub) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll Inf = 1e18;
int main(){
ll n,m,b;
cin>>n>>m;
vector<ll>A(n+2);
A[0] = -Inf, A[n+1] = Inf;
for(int i=0;i<n;i++){
cin>>A[i+1];
}
cin>>b;
ll s=0,p=-1,k=1,w=0;
for(int i=1;i<=n;i++){
int now = A[i];
p++, k--;
while(s > b){
s -= A[i]-A[i-p], p--;
}
while(A[i+k+1]-A[i]+s <= b || A[i+k+1] - A[i] <= A[i] - A[i-p]){
if(A[i+k+1]-A[i]+s <= b)
s += A[i+k+1]-A[i], k++;
else{
s += A[i+k+1] - A[i] - A[i] + A[i-p], p--, k++;
}
}
w = max(w, p+k+1);
// cout<<p<<" "<<k<<" "<<s<<"\n";
s += (p - k + 1) * (A[i+1] - A[i]);
}
cout<<w;
}