Submission #785698

#	Time	Username	Problem	Language	Result	Execution time	Memory
785698		Boas	Rice Hub (IOI11_ricehub)	C++17	68 / 100	1069 ms	1876 KiB

ricehub

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

int besthub(int R, int L, int X[], ll B)
{
  int prev = X[0];
  int prevInx = 0;
  vii fields = {{prev, 1}};
  for (int i = 1; i < R; i++)
  {
    int v = X[i];
    if (v == prev)
    {
      fields[prevInx].second++;
    }
    else
    {
      fields.push_back({v, 1});
      prev = v;
      prevInx++;
    }
  }
  int maxRice = 0;
  for (int i = 0; i < fields.size(); i++)
  {
    const auto &[loc, num] = fields[i];
    int rice = num;
    ll bLeft = B;
    int inxsR = 0;
    int inxsL = 0;
    while (bLeft > 0)
    {
      int diffL = i - inxsL - 1 < 0 ? INT_MAX : loc - fields[i - inxsL - 1].first;
      int diffR = i + inxsR + 1 >= fields.size() ? INT_MAX : fields[i + inxsR + 1].first - loc;
      if (diffL == INT_MAX && diffL == diffR)
        break;
      if (diffL <= diffR)
      {
        int fieldCount = fields[i - inxsL - 1].second;
        inxsL++;
        int maxCost = diffL * fieldCount;
        if (maxCost <= bLeft)
        {
          rice += fieldCount;
          bLeft -= maxCost;
        }
        else
        {
          int maxFields = bLeft / diffL;
          rice += maxFields;
          break;
        }
      }
      else
      {
        int fieldCount = fields[i + inxsR + 1].second;
        inxsR++;
        int maxCost = diffR * fieldCount;
        if (maxCost <= bLeft)
        {
          rice += fieldCount;
          bLeft -= maxCost;
        }
        else
        {
          int maxFields = bLeft / 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:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for (int i = 0; i < fields.size(); i++)
      |                   ~~^~~~~~~~~~~~~~~
ricehub.cpp:37:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |       int 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