Submission #348394

#	Time	Username	Problem	Language	Result	Execution time	Memory
348394		idk321	Rice Hub (IOI11_ricehub)	C++11	32 / 100	16 ms	1920 KiB

ricehub

#include "ricehub.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int besthub(int n, int l, int x[], long long money)
{

  int a = 0;
  int b = 0;
  ll cost = 0;
  int best = 0;
  while (b + 1 < n && cost + x[(b + 1)] - x[0] <= money)
  {
    cost += x[(b + 1)] - x[0];
    b++;
  }
  int left = 0;
  int right = b;
  best = max(best, b - a + 1);
  //cout << "oj " << cost << endl;
  for (int i = 1; i < n; i++)
  {
        cost -= (ll) right * (x[i] - x[i - 1]);
        left++;
        cost += (ll) left * (x[i] - x[i - 1]);
        right--;
        while(cost > money)
        {
            cost -= x[i] - x[a];
            a++;
            left--;
        }
        while(b + 1 < n && x[b + 1] - x[i] + cost < money)
        {
            cost += x[b + 1] - x[i];
            b++;
            right++;
        }
        while (b + 1 < n && x[i] - x[a] > x[b + 1] - x[i])
        {
            cost -= x[i] - x[a];
            a++;
            left--;
            cost += x[b + 1] - x[i];
            b++;
            right++;
        }

        //cout << "oj " << a << " " << b << " " << cost << endl;
        best = max(best, b - a + 1);
  }
  return best;
}

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