Submission #1193135

#TimeUsernameProblemLanguageResultExecution timeMemory
1193135nuutsnoyntonRice Hub (IOI11_ricehub)C++20
68 / 100
1095 ms1348 KiB
#include<bits/stdc++.h> #include "ricehub.h" using ll = long long; using namespace std; ll pre_sum[100002]; ll range_sum(ll lo, ll hi) { if ( lo == 0) return pre_sum[hi]; return pre_sum[hi] - pre_sum[lo - 1]; } int besthub(int R, int L, int X[], long long B){ ll lo, hi, mid, Lo, Hi, mid1, lo1, hi1, lo2, hi2, sum; for (int i = 0; i < R; i ++) { if ( i == 0) pre_sum[i] = X[i]; else pre_sum[i] = pre_sum[i - 1] + X[i]; } ll s; ll max_s = 0; for (int i = 0; i < R; i ++) { lo = 0; hi = R + 1; while ( lo < hi) { mid = (lo + hi)/2; lo1 = 0; hi1 = 1e9 + 1; while ( lo1 < hi1) { mid1 = (lo1 + hi1)/2; Lo = lower_bound(X, X + R, X[i] - mid1) - X; Hi = upper_bound(X, X + R, X[i] + mid1) - X - 1; if ( Hi - Lo + 1 < mid) lo1 = mid1 + 1; else hi1 = mid1; } mid1 =lo1; Lo = lower_bound(X, X + R, X[i] - mid1) - X; Hi = upper_bound(X, X + R, X[i] + mid1) - X - 1; // cout << Hi - Lo + 1 << " " << mid << "" << endl; // cout << mid1 << " " << Lo << " " << Hi << endl; // cout << mid << " " << lo1 << endl; sum =0 ; lo1 = Lo; hi1 = i; lo2 = i; hi2 = Hi; sum = sum + (hi1 - lo1 + 1) * X[i] - range_sum(lo1, hi1); sum = sum + range_sum(lo2, hi2) - (hi2 - lo2 + 1) * X[i]; s = Hi - Lo + 1 - mid; s = s * mid1; sum = sum - s; // cout << mid << " " << sum << "RRR" << endl; if ( sum <= B) lo = mid + 1; else hi = mid; } lo --; //cout << lo << " DONE" << endl; max_s = max(max_s, lo); } return max_s; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...