Submission #113025

#TimeUsernameProblemLanguageResultExecution timeMemory
113025CaroLindaRice Hub (IOI11_ricehub)C++14
0 / 100
17 ms2688 KiB
#include <bits/stdc++.h> #include "ricehub.h" #define lp(i,a,b) for(int i = a ; i < b ; i++) #define ll long long #define pii pair<int,int> #define ff first #define ss second #define pb push_back #define mk make_pair const int inf = 1e9 + 10 ; const int MAXN = 1e5 + 10 ; using namespace std ; int l , r , x[MAXN] ; ll b , pref[MAXN] , suf[MAXN] ; int m(int a , int b) { return (a+b)/2 ; } ll d(int a , int b ) { return abs( x[a] - x[b] ) ; } ll c1(int a , int b) { return pref[b] - pref[a] - (b-a) * d(a,1) ; } ll c2(int a , int b) { return suf[a] - suf[b] - (b-a) * d(b,r) ; } bool test(int tam) { int ini = 1 , fim = tam ; while( fim <= r ) { int now = m(ini,fim) ; if( ( c1( ini , now ) + c2( now , fim ) ) <= b ) return true ; ini ++ , fim++ ; } return false ; } int besthub(int R , int L , int X[] , ll B ) { b = B , r = R , l = L ; lp(i,1,r+1) x[i] = X[i-1] ; sort( x+1 , x+r+1 ) ; lp(i,1,r+1) pref[i] = pref[i-1] + d(i,1) ; for(int i = r ; i > 0 ; i-- ) suf[i] = suf[i+1] + d(i,r) ; int ini = 1 , fim = r , best = 1; while( ini <= fim ) { if( test( m(ini,fim) ) ) { best = m(ini,fim) ; ini = m(ini,fim) + 1 ; } else fim = m(ini,fim) - 1; } return best ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...