Submission #785700

#	Time	Username	Problem	Language	Result	Execution time	Memory
785700		Boas	Rice Hub (IOI11_ricehub)	C++17	68 / 100	1082 ms	2844 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef vector<pair<ll, ll>> vii;

int besthub(int R, int L, int X[], ll B)
{
  ll prev = X[0];
  ll prevInx = 0;
  vii fields = {{prev, 1}};
  for (ll i = 1; i < R; i++)
  {
    ll v = X[i];
    if (v == prev)
    {
      fields[prevInx].second++;
    }
    else
    {
      fields.push_back({v, 1});
      prev = v;
      prevInx++;
    }
  }
  ll maxRice = 0;
  for (ll i = 0; i < fields.size(); i++)
  {
    const auto &[loc, num] = fields[i];
    ll rice = num;
    ll bLeft = B;
    ll inxsR = 0;
    ll inxsL = 0;
    while (bLeft > 0)
    {
      ll diffL = i - inxsL - 1 < 0 ? INT_MAX : loc - fields[i - inxsL - 1].first;
      ll diffR = i + inxsR + 1 >= fields.size() ? INT_MAX : fields[i + inxsR + 1].first - loc;
      if (diffL == INT_MAX && diffL == diffR)
        break;
      if (diffL <= diffR)
      {
        ll fieldCount = fields[i - inxsL - 1].second;
        inxsL++;
        ll maxCost = diffL * fieldCount;
        if (maxCost <= bLeft)
        {
          rice += fieldCount;
          bLeft -= maxCost;
        }
        else
        {
          ll maxFields = bLeft / (ll)diffL;
          rice += maxFields;
          break;
        }
      }
      else
      {
        ll fieldCount = fields[i + inxsR + 1].second;
        inxsR++;
        ll maxCost = diffR * fieldCount;
        if (maxCost <= bLeft)
        {
          rice += fieldCount;
          bLeft -= maxCost;
        }
        else
        {
          ll maxFields = bLeft / (ll)diffR;
          rice += maxFields;
          break;
        }
      }
    }
    if (rice > maxRice)
    {
      maxRice = rice;
    }
  }
  return maxRice;
}

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, ll)':
ricehub.cpp:27:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for (ll i = 0; i < fields.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~
ricehub.cpp:37:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |       ll diffR = i + inxsR + 1 >= fields.size() ? INT_MAX : fields[i + inxsR + 1].first - loc;
      |                  ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

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