Submission #1040004

#TimeUsernameProblemLanguageResultExecution timeMemory
1040004dpsaveslivesRice Hub (IOI11_ricehub)C++17
100 / 100
10 ms3528 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; const int MAXN = 1e5+10; ll pref1[MAXN],pref2[MAXN],arr[MAXN]; int X[5] = {1,2,10,12,14}; int besthub(int R,int L,int X[],ll B){ for(int i = 0;i<R;++i){ arr[i+1] = X[i]; } for(int i = 1;i<=R;++i){ pref1[i] = pref1[i-1]+arr[i]; //-> pref[1] = distance from 1 to X[1] //cout << pref1[i] << "\n"; } pref1[R+1] = L-pref1[R]; /*for(int i = 1;i<=R+1;++i){ pref2[i] = pref2[i-1]+pref1[i]; cout << pref2[i] << "\n"; }*/ int lo = -1, hi = R; while(lo < hi){ int mid = lo+(hi-lo+1)/2; bool good = false; if(mid % 2 == 0){ int i = 1; //number of the first field, one-indexed and all while(i+mid-1 <= R){ int m = (i+(mid/2)); ll cur = pref1[i+mid-1]-pref1[m-1]-(pref1[m-1]-pref1[i-1]); //ll cur = pref1[i+mid]-pref1[m]-(pref1[m]-pref1[i]); //cout << i << " " << cur << " " << mid << "\n"; if(cur <= B){ good = true; break; } ++i; } } else{ int i = 1; //number of the first field, one-indexed and all while(i+mid-1 <= R){ int m = (i+(mid/2)); ll cur = pref1[i+mid-1]-pref1[m]-(pref1[m-1]-pref1[i-1]); //ll cur = pref1[i+mid]-pref1[m+1]-(pref1[m]-pref1[i]); //cout << i << " " << cur << " " << mid << "\n"; if(cur <= B){ good = true; break; } ++i; } } if(good){ lo = mid; } else{ hi = mid-1; } } return lo; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...