Submission #706952

#	Time	Username	Problem	Language	Result	Execution time	Memory
706952		Nhoksocqt1	Rice Hub (IOI11_ricehub)	C++17	100 / 100	14 ms	2884 KiB

ricehub

#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 100005;

ll sum[MAXN], budget;
int dis[MAXN], numField, maxCoord;

ll calcMin(int n) {
    ll res(1e18);
    for (int i = 1; i + n - 1 <= numField; ++i) {
        int j(i + n - 1), mid = (i + j) >> 1;
        ll minNow = 1LL * (mid - i + 1) * dis[mid] - sum[mid] + sum[i - 1];
        minNow += sum[j] - sum[mid] - 1LL * (j - mid) * dis[mid];

        res = min(res, minNow);
    }

    return res;
}

int besthub(int _R, int _L, int _X[], ll _B) {
    numField = _R, maxCoord = _L, budget = _B;
    for (int i = 1; i <= numField; ++i) {
        dis[i] = _X[i - 1];
        sum[i] = sum[i - 1] + dis[i];
    }

    int l(1), r(numField), answer(0);
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(calcMin(mid) <= budget) {
            answer = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    return answer;
}

Compilation message (stderr)

ricehub.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
ricehub.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      |

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