# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
58346 | 2018-07-17T13:59:04 Z | PeppaPig | 쌀 창고 (IOI11_ricehub) | C++14 | 0 ms | 0 KB |
#include "ricehub.h" #include <bits/stdc++.h> using namespace std; const int N = 5e3 + 5; long long sum[N]; long long min(long long a, int b) { return a < b ? a : b; } int besthub(int R, int L, int X[], long long B) { sum[0] = X[0]; for(int i = 0; i < R; i++) sum[i] = sum[i - 1] + X[i]; int res = 0; int l = 0, r = R; while(l <= r) { int mid = (l + r) >> 1; int m = mid >> 1; long long ret = LLONG_MAX; for(int i = 0; i < R - mid + 1; i++) { if(mid == 1) ret = min(ret, 0); if(mid == 2) ret = min(ret, X[i + 1] - X[i]); else { long long t = sum[i + mid - 1] - sum[i + m] - sum[i + m - 1] + i > 0 : sum[i - 1] : 0; if(mid & 1) ret = min(ret, t); else ret = min(ret, t + X[i + m]); } } if(ret <= B) res = mid, l = mid + 1; else r = mid - 1; } return res; }