Submission #792399

#TimeUsernameProblemLanguageResultExecution timeMemory
792399CookieRice Hub (IOI11_ricehub)C++14
100 / 100
14 ms3340 KiB
#include<bits/stdc++.h> #include<fstream> using namespace std; ifstream fin("VNOICUP.INP"); ofstream fout("VNOICUP.OUT"); #define sz(a) (int)a.size() #define ll long long #define pb push_back #define forr(i, a, b) for(int i = a; i < b; i++) #define dorr(i, a, b) for(int i = a; i >= b; i--) #define ld long double #define vt vector #include<fstream> #define fi first #define se second #define pll pair<ll, ll> #define pii pair<int, int> const ld PI = 3.14159265359; using u128 = __uint128_t; //const int x[4] = {1, -1, 0, 0}; //const int y[4] = {0, 0, 1, -1}; const ll mod = 1e9 + 7; const int mxn = 1e5 + 5, mxq = 1e6 + 5, sq = 400; const int base = (1 << 18); const int inf = 1e9, neg = -69420; #include "ricehub.h" ll a[mxn + 1], pref[mxn + 1], b, n; bool ck(int mid){ for(int i = 1; i + mid - 1 <= n; i++){ int id = i + (mid) / 2; ll cand = a[id] * (id - i + 1) - (pref[id] - pref[i - 1]) + (pref[i + mid - 1] - pref[id - 1]) - (a[id] * (i + mid - 1 - id + 1)); if(cand <= b)return(1); } return(0); } int besthub(int R, int L, int X[], long long B) { b = B; n = R; for(int i = 0; i < R; i++)a[i + 1] = X[i]; for(int i = 1; i <= R; i++){ pref[i] = pref[i - 1] + a[i]; } int l = 1, r = R, ans = 0; while(l <= r){ int mid = (l + r) >> 1; if(ck(mid)){ ans = mid; l = mid + 1; }else{ r = mid - 1; } } return(ans); } /* #define MAX_R 1000000 static int R, L; static long long B; static int X[MAX_R]; static int solution; inline void my_assert(int e) {if (!e) abort();} static void read_input() { int i; my_assert(3==scanf("%d %d %lld",&R,&L,&B)); for(i=0; i<R; i++) my_assert(1==scanf("%d",&X[i])); my_assert(1==scanf("%d",&solution)); } int main() { int ans; read_input(); ans = besthub(R,L,X,B); if(ans==solution) printf("Correct.\n"); else printf("Incorrect. Returned %d instead of %d.\n",ans,solution); return 0; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...