Submission #345129

#	Time	Username	Problem	Language	Result	Execution time	Memory
345129		casperwang	Rice Hub (IOI11_ricehub)	C++14	100 / 100	27 ms	2412 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }

const int MAXN = 200000;
vector <long long> pre;

long long cal(int l, int r, int X[]) {
  int p = l + r >> 1;
  long long dis = 0;
  dis += ((long long) X[p] * (p-l+1) - (pre[p] - pre[l-1]));
  dis += (pre[r] - pre[p]) - (long long) X[p] * (r-p);
  return dis;
}

int besthub(int R, int L, int X[], long long B) {
  pre.resize(R);
  pre[0] = X[0];
  for (int i = 1; i < R; i++)
    pre[i] = pre[i-1] + X[i];
  int l = 1, r = R, mid;
  while (l < r) {
    mid = (l + r + 1) >> 1;
    bool flag = 0;
    for (int i = 0; i+mid-1 < R; i++) {
      if (cal(i, i+mid-1, X) <= B) flag = 1;
    }
    if (flag) l = mid;
    else r = mid-1;
  }
  return l;
}

Compilation message (stderr)

ricehub.cpp: In function 'long long int cal(int, int, int*)':
ricehub.cpp:13:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |   int p = l + r >> 1;
      |           ~~^~~

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 26 / 26
• Subtask 4: 32 / 32