| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 172987 | 2020-01-02T22:59:41 Z | FieryPhoenix | Rice Hub (IOI11_ricehub) | C++11 | 0 ms | 0 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <climits>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007
ll besthub(ll R, ll L, ll x[], ll B){
ll X[R+1];
ll ans=1;
for (int i=1;i<=R;i++)
X[i]=x[i-1];
ll r=1,mid=1,cost=0;
for (int i=1;i<=R;i++){
while (r<=R && cost<=B){
r++;
if (r>R)
break;
int newMid=(i+r)/2;
//cout<<mid<<' '<<newMid<<endl;
if (newMid==mid)
cost+=X[r]-X[mid];
else{
ll diff=X[newMid]-X[mid];
cost+=(mid-i+1)*diff;
cost-=(r-1-newMid+1)*diff;
cost+=X[r]-X[newMid];
mid=newMid;
}
}
ans=max(ans,r-i);
//cout<<"RANGE "<<i<<' '<<r<<" cost "<<cost<<endl;
int newMid=(i+1+r)/2;
//cout<<mid<<' '<<newMid<<endl;
if (newMid==mid)
cost-=(X[mid]-X[i]);
else{
ll diff=X[newMid]-X[mid];
cost+=(mid-(i+1)+1)*diff;
cost-=(min(r,R)-newMid+1)*diff;
cost-=(X[mid]-X[i]);
mid=newMid;
}
}
return ans;
}