Submission #348395

#	Time	Username	Problem	Language	Result	Execution time	Memory
348395		idk321	Rice Hub (IOI11_ricehub)	C++11	49 / 100	17 ms	748 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) || (b + 1 < n && x[i] - x[a] > x[b + 1] - x[i]))
        {
            if (x[b + 1] - x[i] + cost < money)
            {
                cost += x[b + 1] - x[i];
                b++;
                right++;
            } else
            {
                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: 17 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 26
• Subtask 4: 32 / 32