oj.uz

Submission #981047

# Submission time Handle Problem Language Result Execution time Memory
981047 2024-05-12T18:21:16 Z kilkuwu Rice Hub (IOI11_ricehub) C++17
100 / 100
 9 ms 4508 KB 
#include "ricehub.h"

#include <bits/stdc++.h>

int besthub(int R, int L, int X[], long long B) { 
  std::vector<int64_t> pref(R + 1);
  for (int i = 0; i < R; i++) {
    pref[i + 1] = pref[i] + X[i];
  }


  auto check = [&](int mid) -> bool {
    // 3 / 2 = 1
    // 4 / 2 = 2 
    // 0 1 2 3 
    int elem = mid / 2;
    int num_left = elem;
    int num_right = mid - num_left;
    for (int i = 0; i + mid <= R; i++) {
      int64_t me = X[i + elem];
      auto sum_left = pref[i + elem] - pref[i]; // i -> 
      auto sum_right = pref[i + mid] - pref[i + elem];
      auto ans = me * num_left - sum_left + sum_right - me * num_right;
      if (ans <= B) return true;
    } 
    return false;
  };

  int ans = 0;
  int lb = 1, rb = R;

  while (lb <= rb) {
    int mb = (lb + rb) / 2;
    if (check(mb)) {
      ans = mb;
      lb = mb + 1;
    } else {
      rb = mb - 1;
    }
  }

  return ans;
}

#ifdef LOCAL 
#include "ricehub.h"
#include <stdio.h>
#include <stdlib.h>

#define MAX_R  1000000

static int R, L;
static long long B;
static int X[MAX_R];
static int solution;

inline 
void my_assert(int e) {if (!e) abort();}

static void read_input()
{
  int i;
  my_assert(3==scanf("%d %d %lld",&R,&L,&B));
  for(i=0; i<R; i++)
    my_assert(1==scanf("%d",&X[i]));
  my_assert(1==scanf("%d",&solution));
}

int main()
{
  int ans;
  read_input();
  ans = besthub(R,L,X,B);
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect.  Returned %d instead of %d.\n",ans,solution);

  return 0;
}
#endif

Subtask #1
17.0 / 17.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 460 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 9 ms 4508 KB Output is correct
4 Correct 9 ms 4444 KB Output is correct
5 Correct 5 ms 3384 KB Output is correct
6 Correct 5 ms 3164 KB Output is correct
7 Correct 8 ms 4184 KB Output is correct
8 Correct 8 ms 4188 KB Output is correct
9 Correct 6 ms 3164 KB Output is correct
10 Correct 5 ms 3160 KB Output is correct
11 Correct 9 ms 4440 KB Output is correct
12 Correct 9 ms 4444 KB Output is correct
13 Correct 6 ms 3420 KB Output is correct
14 Correct 5 ms 3420 KB Output is correct
15 Correct 7 ms 3828 KB Output is correct
16 Correct 7 ms 3928 KB Output is correct
17 Correct 8 ms 4184 KB Output is correct
18 Correct 8 ms 4188 KB Output is correct
19 Correct 9 ms 4320 KB Output is correct
20 Correct 9 ms 4188 KB Output is correct