oj.uz

Submission #820145

# Submission time Handle Problem Language Result Execution time Memory
820145 2023-08-10T20:27:50 Z nemethm Rice Hub (IOI11_ricehub) C++17
17 / 100
 1000 ms 3524 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;
      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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1065 ms 3524 KB Time limit exceeded
2 Halted 0 ms 0 KB -