oj.uz

Submission #168928

# Submission time Handle Problem Language Result Execution time Memory
168928 2019-12-17T08:38:20 Z AlexLuchianov Rice Hub (IOI11_ricehub) C++14
0 / 100
 405 ms 3064 KB 
#include "ricehub.h"

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 100000;
int v[1 + nmax], n;
ll sum[1 + nmax];

///returns position of the last farm with coordinate lower (or equal) than target

int lowerthan(int target){
  int x = 0;
  for(int jump = (1 << 20); 0 < jump; jump /= 2)
    if(x + jump <= n && v[x + jump] <= target)
      x += jump;
  return x;
}

int tryit(int pos, int dist, ll budget){
  int pos2 = lowerthan(v[pos] + dist), pos3 = lowerthan(v[pos] - dist - 1) + 1;

  int result = ((sum[pos2] - sum[pos - 1]) - (pos2 - pos + 1) * v[pos]);
  int result2 = (pos - pos3 + 1) * v[pos] - (sum[pos] - sum[pos3 - 1]);

  return result + result2 <= budget;
}

int solve(int pos, ll budget){
  int dist = 0;
  for(int jump = (1 << 30); 0 < jump; jump /= 2){
    if(tryit(pos, dist + jump, budget))
      dist += jump;
  }
  dist++;

  int pos2 = lowerthan(v[pos] + dist), pos3 = lowerthan(v[pos] - dist - 1) + 1;

  int result = ((sum[pos2] - sum[pos - 1]) - (pos2 - pos + 1) * v[pos]);
  int result2 = (pos - pos3 + 1) * v[pos] - (sum[pos] - sum[pos3 - 1]);
  result = result + result2;

  return (pos2 - pos3 + 1) - 1 - (result - budget + 1) / dist;
}

int besthub(int R, int L, int X[], long long B)
{
  n = R;
  for(int i = 1;i <= n; i++)
    v[i] = X[i - 1];
  for(int i = 1;i <= n; i++)
    sum[i] = sum[i - 1] + v[i];

  int result = 0;
  for(int i = 1;i <= n; i++) {
    int result2 = solve(i, B);
    result = MAX(result, result2);
  }
  return result;
}

Subtask #1
0 / 17.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 804 KB Output is correct
2 Correct 64 ms 760 KB Output is correct
3 Incorrect 405 ms 3064 KB Output isn't correct
4 Halted 0 ms 0 KB -