제출 #336113

#제출 시각아이디문제언어결과실행 시간메모리
336113knightron0쌀 창고 (IOI11_ricehub)C++14
42 / 100
15 ms1516 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(long long x, long long b){ for(long long i= 1;i<=n-x+1;i++){ vector<long long> 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(long long m: md){ long long sum1 = (long long)pref[m]-(long long)pref[i-1]; sum1 *= -1; sum1 += (long long)(m-(i-1))*(long long)a[m]; long long sum2 = (long long)pref[i+x-1]-(long long)pref[m]; sum2 -= (long long)(i+x-1-m)*(long long)a[m]; long long 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((long long) mid, b)){ lo = mid+1; } else { hi = mid-1; } } if(!check(lo, b)){ return hi; } 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...