제출 #1273351

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273351		lamlamlam	Rice Hub (IOI11_ricehub)	C++20	100 / 100	9 ms	1092 KiB

ricehub

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

#include "ricehub.h"
#define ll long long
struct Data {
    deque<int> dq;
    ll sum = 0, lower_sum = 0;
    void push_back(int x){
        dq.push_back(x);
        int sz = dq.size(), mid = mid = (sz-1)/2;
        if(sz%2) lower_sum += dq[mid];
        sum += x;
    }
    void pop_front(){
        int sz = dq.size(), mid = (sz-1)/2;
        if(!sz) return;
        auto tmp = dq.front(); dq.pop_front(); sz--; mid = (sz-1)/2;
        sum -= tmp; lower_sum -= tmp;
        if(sz%2) lower_sum += dq[mid];
    }
    ll get_weight(){
        int sz = dq.size(), mid = (sz-1)/2;
        if(!sz) return 0;
        ll sus = dq[mid]*(mid+1) - lower_sum + (sum - lower_sum) - dq[mid]*(sz-mid-1);
        return sus;
    }
    int get_mid(){
        int sz = dq.size(), mid = (sz-1)/2;
        if(!sz) return 0;
        return dq[mid];
    }
};
int besthub(int R, int L, int X[], long long B)
{
    Data dq;
    int l = 0, r = 0, mid, sz, ans = 0, best_ans = 0;
    while(r<R){
        dq.push_back(X[r]);
        while(dq.get_weight()>B) dq.pop_front();
//        cerr << r << ' ' << r-dq.dq.size()+1 << ' ' << dq.get_weight() << ' ' << dq.get_mid() << ' ' << dq.dq.size() << endl;
        int sz = dq.dq.size();
        if(sz>best_ans){
            best_ans = sz;
            ans = dq.get_mid();
        }
        r++;
    }
    return best_ans;
}

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