Submission #820145

#	Time	Username	Problem	Language	Result	Execution time	Memory
820145		nemethm	Rice Hub (IOI11_ricehub)	C++17	17 / 100	1065 ms	3524 KiB

ricehub

    #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 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 26
• Subtask 4: 0 / 32