제출 #336106

#제출 시각아이디문제언어결과실행 시간메모리
336106knightron0쌀 창고 (IOI11_ricehub)C++14
68 / 100
17 ms1556 KiB
#include <bits/stdc++.h> #include "ricehub.h" #define pb push_back using namespace std; const int MOD = 1e9 + 7; const int MAXN = 1e5 + 5; int a[MAXN], pref[MAXN]; int n; bool check(int x, int b){ for(int i= 1;i<=n-x+1;i++){ vector<int> md; if(x & 1){ md.pb((i + i +x-1)/2); } else { md.pb((i + i +x-1)/2); md.pb(((i + i +x-1)/2)+1); } for(int m: md){ int sum1 = pref[m]-pref[i-1]; sum1 *= -1; sum1 += (m-(i-1))*a[m]; int sum2 = pref[i+x-1]-pref[m]; sum2 -= (i+x-1-m)*a[m]; int sum = sum1+sum2; if(sum <= b){ return true; } } } return false; } int besthub(int r, int l, int x[], long long b) { n = r; pref[0] = 0; for(int i= 1;i<=n;i++){ a[i] = x[i-1]; pref[i] = pref[i-1] + a[i]; } int lo = 1; int hi = n; while(lo <= hi){ int mid = lo+(hi-lo)/2; if(check(mid, b)){ lo = mid+1; } else { hi = mid-1; } } if(!check(lo, b)){ return hi; } return lo; } // signed main() { // ios_base::sync_with_stdio(false); // cin.tie(NULL); // #ifndef ONLINE_JUDGE // freopen("input.txt", "r", stdin); // #endif // int m, k; // cin>>n>>m>>k; // pref[0] = 0; // for(int i=1;i<=n;i++){ // cin>>a[i]; // pref[i] = pref[i-1] + a[i]; // } // 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...