#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+1]-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 |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
0 ms |
348 KB |
Output is correct |
| 20 |
Correct |
0 ms |
348 KB |
Output is correct |
| 21 |
Correct |
1 ms |
348 KB |
Output is correct |
| 22 |
Correct |
1 ms |
348 KB |
Output is correct |
| 23 |
Correct |
1 ms |
348 KB |
Output is correct |
| 24 |
Correct |
1 ms |
348 KB |
Output is correct |
| 25 |
Correct |
1 ms |
348 KB |
Output is correct |
| 26 |
Correct |
1 ms |
452 KB |
Output is correct |
| 27 |
Correct |
1 ms |
348 KB |
Output is correct |
| 28 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
3 ms |
348 KB |
Output is correct |
| 4 |
Correct |
3 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
344 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
2 ms |
348 KB |
Output is correct |
| 8 |
Correct |
2 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
2 ms |
348 KB |
Output is correct |
| 12 |
Correct |
2 ms |
348 KB |
Output is correct |
| 13 |
Correct |
3 ms |
348 KB |
Output is correct |
| 14 |
Correct |
3 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
344 KB |
Output is correct |
| 16 |
Correct |
1 ms |
344 KB |
Output is correct |
| 17 |
Correct |
2 ms |
348 KB |
Output is correct |
| 18 |
Correct |
2 ms |
348 KB |
Output is correct |
| 19 |
Correct |
3 ms |
348 KB |
Output is correct |
| 20 |
Correct |
3 ms |
348 KB |
Output is correct |
| 21 |
Correct |
35 ms |
604 KB |
Output is correct |
| 22 |
Correct |
37 ms |
600 KB |
Output is correct |
| 23 |
Correct |
98 ms |
600 KB |
Output is correct |
| 24 |
Correct |
91 ms |
600 KB |
Output is correct |
| 25 |
Correct |
91 ms |
604 KB |
Output is correct |
| 26 |
Correct |
92 ms |
604 KB |
Output is correct |
| 27 |
Correct |
139 ms |
600 KB |
Output is correct |
| 28 |
Correct |
108 ms |
600 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
501 ms |
980 KB |
Output is correct |
| 2 |
Correct |
486 ms |
1236 KB |
Output is correct |
| 3 |
Execution timed out |
1029 ms |
4812 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
