oj.uz

답안 #168929

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
168929 2019-12-17T08:42:51 Z AlexLuchianov 쌀 창고 (IOI11_ricehub) C++14
0 / 100
 484 ms 2316 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 n;
ll v[1 + nmax], 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;
}

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

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

  return result + result2 <= budget;
}

ll 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;

  ll result = ((sum[pos2] - sum[pos - 1]) - (pos2 - pos + 1) * v[pos]);
  ll 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 4 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 760 KB Output is correct
2 Correct 69 ms 760 KB Output is correct
3 Incorrect 484 ms 2316 KB Output isn't correct
4 Halted 0 ms 0 KB -