#pragma once
#include <iostream>
#include <set>
#include <vector>
using namespace std;
int besthub(int r, int l, int x[], long long b)
{
int ans=0;
vector<long long> vp,pre={0};
vp.push_back(-3e15);
for(int i=0;i<r;i++)
vp.push_back(x[i]);
vp.push_back(3e15);
for(auto i:vp)
pre.push_back(pre.back()+i);
for(int i=1;i<=r;i++)
{
// binary search on cnt
int cnt_s=1;
int cnt_e=r+1;
while(cnt_s+1<cnt_e)
{
int mid=(cnt_s+cnt_e)/2;
bool pos=0;
for(int take=1;take<=i and take<=mid;take++)
{
if((r-i)>=(mid-take))
{
// we take
// a[i-take+1] . .. a[i] // sum of this is
long long cur=0;
long long sum_b=pre[i+1]-pre[i-take+1];
cur+=((take*vp[i])-sum_b);
// a[i+1] .. a[i+(mid-take)]
long long sum_f=pre[i+mid-take+2]-pre[i+1];
cur+=(sum_f-((mid-take)*vp[i]));
if(cur<=b)
{
// cout<<"mid "<<mid<<' '<<take<<' '<<cur<<endl;
// cout<<sum_b<<' '<<sum_f<<endl;
pos=1;
break;
}
}
}
if(pos)
{
cnt_s=mid;
}
else
{
cnt_e=mid;
}
}
// int cnt=1;
// long long tm=0;
// int l=i-1;
// int r=i+1;
// while(min(vp[i]-vp[l],vp[r]-vp[i])<=(b-tm))
// {
// tm+=min(vp[i]-vp[l],vp[r]-vp[i]);
// if((vp[i]-vp[l])==min(vp[i]-vp[l],vp[r]-vp[i]))
// {
// cnt++;
// l--;
// }
// else
// {
// cnt++;
// r++;
// }
// }
ans=max(ans,cnt_s);
}
return ans;
}
Compilation message
ricehub.cpp:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
558 ms |
984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
