Submission #1289301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289301		harryleee	Rice Hub (IOI11_ricehub)	C++20	0 / 100	0 ms	412 KiB

ricehub

#include<bits/stdc++.h>
using namespace std;
int n;
vector<pair<long long, long long>> a (1, {0, 0});
pair<long long, long long> pre[1000001];

struct khanhbang{
    long long earn, cost, next_len;
    inline khanhbang(){
        earn = cost = 0;
        next_len = 2e9;
    }
};

khanhbang rice(int pos, int len){
    int lo = 1, hi = pos, left = -1, right = -1;
    while(lo <= hi){
        int mid = (lo + hi) >> 1;
        if (pos - a[mid].first <= len) left = mid, hi = mid - 1;
        else lo = mid + 1;
    }
    lo = pos, hi = n - 1;
    while(lo <= hi){
        int mid = (lo + hi) >> 1;
        if (a[mid].first - pos <= len) right = mid, lo = mid + 1;
        else hi = mid - 1;
    }
    khanhbang res;
    res.earn = pre[right].second - pre[left - 1].second;
    res.cost = (pre[pos].second - pre[left - 1].second) * pos - (pre[pos].first - pre[left - 1].first);
    res.cost += (pre[right].first - pre[pos].first) - (pre[right].second - pre[pos].second) * pos;
    if (left > 1) res.next_len = min(res.next_len, a[left - 1].first);
    if (right < n - 1) res.next_len = min(res.next_len, a[right + 1].first);
    return res;
}

long long besthub(int r, int l, int x[], long long b){
    n = r;
    long long res = 0;
    int cnt = 1;
    for (int i = 1; i < n; ++i){
        if (x[i] != x[i - 1]){
            a.push_back({x[i - 1], cnt});
            cnt = 0;
        }
        cnt++;
    }
    a.push_back({x[n - 1], cnt});
    n = a.size();

    for (int i = 1; i < n; ++i){
        pre[i].first = a[i].first + pre[i - 1].first;
        pre[i].second = a[i].second + pre[i - 1].second;
    }

    for (int i = 1; i < n; ++i){
        int lo = 0, hi = max(a[n - 1].first - a[i].first, a[i].first - a[1].first);
        khanhbang ans;
        while(lo <= hi){
            int mid = (lo + hi) >> 1;
            khanhbang k = rice(a[i].first, mid);
            if (k.cost <= b) ans = k, lo = mid + 1;
            else hi = mid - 1;
        }
        long long earn = ans.earn;
        long long left = b - ans.cost;
        if (ans.next_len != 2e9) earn += left / ans.next_len;
        res = max(res, earn); 
    }
    return res;
}

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