oj.uz

Submission #820153

# Submission time Handle Problem Language Result Execution time Memory
820153 2023-08-10T20:36:24 Z nemethm Rice Hub (IOI11_ricehub) C++17
100 / 100
 11 ms 1748 KB 
    #include "ricehub.h"
    #include <bits/stdc++.h>
     
    using namespace std;
     
    using ll = long long int;
     
    int besthub(int R, int L, int X[], long long B)
    {
      int l = 1, r = R + 1;
      while(l + 1 < r){
        int m = (l + r + 1) / 2;
        ll cost = 0;
        int base = (m) / 2;
        int b = 0, j = m - 1;
        for(int i = 0; i < m; ++i){
          cost += abs(X[base] - X[i]);
        }
        bool ok = cost <= B;
        while(!ok && j < R - 1){
          ll x = X[base + 1] - X[base];
          cost += x * (base + 1 - b);
          cost -= x * (j - base);
          cost -= X[base] - X[b] + x;
          ++b; ++j; ++base;
          cost += X[j] - X[base];
          //cerr << b << " " << j << " " << base << " " << cost << endl;
          if(cost <= B){
            ok = true;
          }
        }
        if(ok){
          l = m;
        }
        else{
          r = m;
        }
      }
      return l;
    }

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 Correct 1 ms 316 KB Output is correct
5 Correct 0 ms 316 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 312 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 312 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 312 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

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

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 10 ms 1744 KB Output is correct
4 Correct 11 ms 1748 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 5 ms 840 KB Output is correct
7 Correct 9 ms 1392 KB Output is correct
8 Correct 9 ms 1364 KB Output is correct
9 Correct 5 ms 724 KB Output is correct
10 Correct 5 ms 724 KB Output is correct
11 Correct 10 ms 1748 KB Output is correct
12 Correct 10 ms 1748 KB Output is correct
13 Correct 5 ms 836 KB Output is correct
14 Correct 5 ms 836 KB Output is correct
15 Correct 10 ms 1364 KB Output is correct
16 Correct 7 ms 1320 KB Output is correct
17 Correct 9 ms 1576 KB Output is correct
18 Correct 9 ms 1492 KB Output is correct
19 Correct 9 ms 1636 KB Output is correct
20 Correct 9 ms 1600 KB Output is correct