Submission #1245502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245502		Minbaev	Rice Hub (IOI11_ricehub)	C++20	68 / 100	13 ms	2376 KiB

ricehub

 #include "ricehub.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define pb      push_back
#define all(x)  x.begin(),x.end()
#define ar      array
#define mrand(a, b)   uniform_int_distribution<int>(a, b)(rng)

template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}

template<class T> using ste = tree<T, null_type, less_equal<T>,
rb_tree_tag, tree_order_statistics_node_update>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

namespace FAST {
    template<typename T, typename F>
    istream &operator>>(istream &cin, pair<T, F> &p) {
        cin >> p.first >> p.second;
        return cin;
    }

    template<typename T, typename F>
    ostream &operator<<(ostream &cout, pair<T, F> &p) {
        cout << p.first << ' ' << p.second;
        return cout;
    }

    template<typename T>
    istream &operator>>(istream &cin, vector<T> &a) {
    for (T &i: a) cin >> i;
        return cin;
    }

    template<typename T>
    ostream &operator<<(ostream &cout, vector<T> &a) {
          for (T i: a) cout << i << ' ';
        return cout;
    }

    template<typename T>
    istream &operator>>(istream &cin, deque<T> &a) {
        for (T &i: a) cin >> i;
        return cin;
    }

    template<typename T>
    ostream &operator<<(ostream &cout, deque<T> &a) {
        for (T i: a) cout << i << ' ';
        return cout;
    }
}
using namespace FAST;

const long long inf = 1e17 + 7;
const int mod = 1e9 + 7;
const int md = 998244353;

int besthub(int R, int L, int X[], long long B)
{

    vector<long long>pref(R+1), suff(R+2);
    for(int i = 0;i<R;i++){
        pref[i] = ((i == 0) ? 0 : pref[i-1]);
        pref[i] += ((i == 0) ? 0 : (X[i] - X[i-1]) * i);
    }

    for(int i = R-1;i>=0;i--){
        suff[i] = suff[i+1];
        suff[i] += ((i == R-1) ? 0 : (X[i+1] - X[i]) * (R - i - 1));
    }


    int res = 1;
    for(int i = 0;i<R;i++){
        int l = 0, r = i-1, ans = -1;
        while(l <= r){
            long long mid = (l + r) / 2;

            long long sum = 0, u;
            u = i - (i-mid) / 2;
            sum = pref[u] + suff[u];
            if(mid > 0){
                sum -= 0ll + pref[mid] + mid * (X[u] - X[mid]);
            }
            if(mid < R - 1){
                sum -= 0ll + suff[i] + (R - i - 1) * (X[i] - X[u]);
            }

            // if(i == R - 1 && mid == R - 3)cout << sum << "\n";

            if(sum <= B){
                r = mid - 1;
                ans = mid;
            }
            else l = mid + 1;
        }

        if(ans != -1){
            umax(res, (i - ans + 1));
        }
    }

    return res;

}

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 26 / 26
• Subtask 4: 0 / 32