oj.uz

Submission #785692

# Submission time Handle Problem Language Result Execution time Memory
785692 2023-07-17T13:08:37 Z Boas Rice Hub (IOI11_ricehub) C++17
17 / 100
 1000 ms 2856 KB 
#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 bestLoc = -1;
  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)
      {
        inxsL++;
        int fieldCount = fields[i - inxsL - 1].second;
        int maxCost = diffL * fieldCount;
        if (maxCost <= bLeft)
        {
          rice += fieldCount;
          bLeft -= maxCost;
        }
        else
        {
          int maxFields = bLeft / diffL;
          rice += maxFields;
          break;
        }
      }
      else
      {
        inxsR++;
        int fieldCount = fields[i + inxsR + 1].second;
        int maxCost = diffR * fieldCount;
        if (maxCost <= bLeft)
        {
          rice += fieldCount;
          bLeft -= maxCost;
        }
        else
        {
          int maxFields = bLeft / diffR;
          rice += maxFields;
          break;
        }
      }
    }
    if (rice > maxRice)
    {
      maxRice = rice;
      bestLoc = loc;
    }
  }
  return maxRice;
}

Compilation message

ricehub.cpp: In function 'int besthub(int, int, int*, ll)':
ricehub.cpp:29: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]
   29 |   for (int i = 0; i < fields.size(); i++)
      |                   ~~^~~~~~~~~~~~~~~
ricehub.cpp:39: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]
   39 |       int diffR = i + inxsR + 1 >= fields.size() ? INT_MAX : fields[i + inxsR + 1].first - loc;
      |                   ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
ricehub.cpp:27:7: warning: variable 'bestLoc' set but not used [-Wunused-but-set-variable]
   27 |   int bestLoc = -1;
      |       ^~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Incorrect 1 ms 308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 2 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 852 KB Output is correct
2 Correct 7 ms 852 KB Output is correct
3 Execution timed out 1068 ms 2856 KB Time limit exceeded
4 Halted 0 ms 0 KB -