제출 #1291821

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291821		Math4Life2020	모임들 (IOI18_meetings)	C++20	0 / 100	5593 ms	2424 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>; using ti = array<ll,3>;
const ll INF = 1e18;


vector<ll> gseg(vector<ll> H) { //get segment values
    ll N = H.size();
    ll xl = 0; ll xr = N-1;
    if (H.size()==0) {
        return vector<ll>(0);
    }
    set<pii> hpmax; //h pair max
    for (ll i=0;i<N;i++) {
        hpmax.insert((pii){H[i],i});
    }
    ll T = 0; //# of iteration
    vector<ll> v1,v2; //val1/val2 vectors
    while (xl<=xr) {
        assert(!hpmax.empty());
        auto A0 = *(--hpmax.end()); hpmax.erase(--hpmax.end());
        ll hmax = A0.first; ll x = A0.second;
        assert(x>=0 && x<N);
        if (x<xl || xr<x) {
            continue; //break loop & restart
        }
        T++;
        ll a = (x-xl); ll b = (xr-x);
        if (a<b) {
            //recursion call on left
            vector<ll> rcall;
            for (ll x0=xl;x0<x;x0++) {
                rcall.push_back(H[x0]);
            }
            vector<ll> qryL = gseg(rcall);
            if (qryL.size()==0) {
                qryL.push_back(0);
            }
            ll val1 = qryL[0]+hmax*(xr-x+1);
            ll val2 = (x-xl+1)*hmax;
            v1.push_back(val1);
            v2.push_back(val2);
            xl = x+1;
        } else {
            //instead call on right
            vector<ll> rcall;
            for (ll x0=x;x0<xr;x0++) {
                rcall.push_back(H[x0]);
            }
            vector<ll> qryL = gseg(rcall);
            if (qryL.size()==0) {
                qryL.push_back(0);
            }
            ll val1 = qryL[0]+hmax*(x-xl+1);
            ll val2 = (xr-x+1)*hmax;
            v1.push_back(val1);
            v2.push_back(val2);
            xr = x-1;
        }
    }
    assert(T==v1.size());
    assert(T==v2.size());
    vector<ll> ansv;
    ansv.push_back(0);
    for (ll t=(T-1);t>=0;t--) {
        ansv.push_back(min(v1[t],v2[t]+ansv.back()));
    }
    vector<ll> iansv;
    for (ll t=0;t<=T;t++) {
        iansv.push_back(ansv[T-t]);
    }
    return iansv;
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    ll N = H.size();
    ll Q = L.size();
    vector<ll> ans(Q);
    for (ll q=0;q<Q;q++) {
        vector<ll> Hqry;
        for (ll x=L[q];x<=R[q];x++) {
            Hqry.push_back(H[x]);
        }
        ans[q]=gseg(Hqry)[0];
    }
    return ans;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40