oj.uz

Submission #717898

# Submission time Handle Problem Language Result Execution time Memory
717898 2023-04-02T20:03:57 Z thimote75 Rice Hub (IOI11_ricehub) C++14
0 / 100
 3 ms 468 KB 
#include "ricehub.h"

#include <bits/stdc++.h>
#define num long long
#define inf 1e18

using namespace std;

vector<int> X;

int _besthub (int R, int L, num B) {
  int mxCount = 0;

  int left  = 0;
  int right = 0;
  num cost  = 0;
  
  for (int idx = 0; idx < R; idx ++) {
      //printf("a%d: %d %d [%lld]\n", idx, left, right, cost);
    while (cost > B) {
      if (left == right) {
        left = idx;
        right = idx;
        cost = 0;
        break;
      }

      num dlc = X[left ] - X[idx];
      num drc = X[right] - X[idx];

      cost -= max(dlc, drc);
      if (dlc >= drc) left ++;
      else right --;
    }
      //printf("b%d: %d %d [%lld]\n", idx, left, right, cost);

    while (right != R - 1) {
      //printf("bs%lld %d %d", cost, X[right + 1] - X[idx], X[right + 1] - X[idx] - (X[idx] - X[left]));
      if (X[right + 1] - X[idx] + cost <= B) {
        //printf("br\n");
        cost += X[right + 1] - X[idx];
        right ++;
      } else if (X[right + 1] - X[idx]
              - (X[idx] - X[left])
              + cost <= B) {
        //printf("bl\n");
        cost += X[right + 1] - X[idx] - (X[idx] - X[left]);
        right ++;
        left ++;
      } else break ;
      //printf("be%lld %d %d\n", cost, X[right + 1] - X[idx], X[right + 1] - X[idx] - (X[idx] - X[left]));
    }
      //printf("c%d: %d %d [%lld]\n", idx, left, right, cost);

    if (idx + 1 != R) {
      num delta = X[idx + 1] - X[idx];

      cost += delta * (idx - left  + 1);
      cost -= delta * (right - idx);
    }
      //printf("d%d: %d %d [%lld]\n", idx, left, right, cost);
    mxCount = max(mxCount, right - left + 1);
  }

  return mxCount;
}

int besthubnaive(int R, int L, int X[], num B)
{
    int mxCount = 0;
 
    for (int idx = 0; idx < R; idx ++) {
      int left  = idx - 1;
      int right = idx + 1;
 
      num cost  = 0;
      int count = 1;
      while (true) {
        int dcl = left == -1 ? inf : abs(X[left]  - X[idx]);
        int dcr = right == R ? inf : abs(X[right] - X[idx]);
 
        if (min(dcl, dcr) + cost > B) break ;
        cost  += min(dcl, dcr);
        count ++;
        
        if (dcl <= dcr) left --;
        else right ++;
      }

      mxCount = max(count, mxCount);
    }
 
    return mxCount;
}
int besthub(int R, int L, int _X[], num B)
{
  X.resize(R);
  for (int i = 0; i < R; i ++)
    X[i] = _X[i];
  int res = _besthub(R, L, B);

  return res;
  /*if (res != besthubnaive(R, L, _X, B)) {
    //printf("%d %d %lld\n", R, L, B);
    for (int u : X)
      //printf("%d\n", u);
    //printf("%d\n", besthubnaive(R, L, _X, B));
    exit(1);
  }

  exit(0);*/
}

Subtask #1
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 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 32.0

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