Submission #261550

#TimeUsernameProblemLanguageResultExecution timeMemory
261550oscarsierra12Rice Hub (IOI11_ricehub)C++14
17 / 100
209 ms2680 KiB
#include "ricehub.h" #include <stdio.h> #include <stdlib.h> #include <iostream> using namespace std ; const int N = 2e5 ; long long ac[N], ac2[N] ; int besthub(int R, int L, int X[], long long B) { for ( int i = 1 ; i < R ; ++i ) ac[i] = ac[i-1] + 1ll * (X[i] - X[i-1]) * i; for ( int i = R-2 ; i >= 0 ; --i ) ac2[i] = ac2[i+1] + 1ll * (X[i+1] - X[i]) * (R-i-1) ; int ans = 0 ; for ( int i = 0 ; i < R ; ++i ) { int lw = i, hg = R-1 ; while ( lw <= hg ) { int mid = (lw + hg) >> 1 ; int lw2 = i, hg2 = mid ; int mid2 ; long long cost ; while ( lw2 < hg2 ) { mid2 = (lw2 + hg2) >> 1 ; cost = ac[mid2] - 1ll * i * (X[mid2] - X[i]) - ac[i] + ac2[mid2] - 1ll * (R-mid-1) * (X[mid] - X[mid2]) - ac2[mid]; mid2++ ; long long cost2 = ac[mid2] - 1ll * i * (X[mid2] - X[i]) - ac[i] + ac2[mid2] - 1ll * (R-mid-1) * (X[mid] - X[mid2]) - ac2[mid]; if ( cost > cost2 ) lw2 = mid2 ; else hg2 = mid2-1 ; } mid2 = lw2 ; cost = ac[mid2] - 1ll * i * (X[mid2] - X[i]) - ac[i] + ac2[mid2] - 1ll * (R-mid-1) * (X[mid] - X[mid2]) - ac2[mid]; // cout << i << " " << mid2 << " " <<mid << " cost " << cost << " = " << ac[mid2] - 1ll * i * (X[mid2] - X[i]) - ac[i] << " + " << ac[mid] - 1ll * mid2 * (X[mid] - X[mid2]) - ac[mid2] << endl ; if ( cost <= B ) lw = mid+1 ; else hg = mid-1 ; } // cout << i << " " << hg << endl ; ans = max ( ans, hg - i + 1 ) ; } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...