oj.uz

Submission #488972

# Submission time Handle Problem Language Result Execution time Memory
488972 2021-11-21T00:21:44 Z fun_day Rice Hub (IOI11_ricehub) C++14
17 / 100
 50 ms 1604 KB 
#include <bits/stdc++.h>

using namespace std;

int besthub(int R, int L, int X[] , long long B){
  vector<long long> pref(R);
  for(int i = 0 ; i < R ; i++){
    if(i == 0) pref[i] = (long long) X[i];
    else pref[i] = pref[i - 1] + (long long) X[i];
  }
  int best = 0;
  for(int i = 1 ; i < R ; i++){
    int l = 0 , r = i;
    int ans = 0;
    while(l <= r){
      int mid = l + (r - l) / 2;
      int used = i - mid;
      long long sum = X[i] * used  - (pref[i - 1] - (mid > 0 ? pref[mid - 1] : 0));
      long long keep = B - sum;
      int left = i , right = R - 1;
      int here = 0;
      while(left <= right){
        int middle = left + (right - left) / 2;
        int cur = middle - i;
        long long s = pref[middle] - pref[i] - X[i] * cur;
        if(s + sum <= B){
          here = max(here , cur);
          left = middle + 1;
        }
        else{
          right = middle - 1;
        }
      }
      if(keep >= 0){
        ans = max(ans , here + used);        
        r = mid - 1;
      }
      else{
        l = mid + 1;        
      }
    }
    best = max(best , ans);
    if(best == R - 1) break;
  }
  return best + 1;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 304 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 0 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 0 ms 204 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Incorrect 1 ms 204 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 216 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 216 KB Output is correct
8 Correct 1 ms 216 KB Output is correct
9 Correct 0 ms 216 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Incorrect 1 ms 204 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 460 KB Output is correct
2 Correct 9 ms 568 KB Output is correct
3 Correct 11 ms 1604 KB Output is correct
4 Incorrect 50 ms 1588 KB Output isn't correct
5 Halted 0 ms 0 KB -