제출 #1018268

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1018268		vjudge1	모임들 (IOI18_meetings)	C++17	19 / 100	5563 ms	9428 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using ii = pair <ll, ll>;

vll minimum_costs (vi H, vi l, vi r) {
    vll ve(H.begin(), H.end());
    ll n = ve.size();
    ll Q = l.size();
    vll ans(Q, -15);
    for (ll q = 0; q < Q; q++) {
        vll lh(n), rh(n);
        {vll stkVal;
        vll stkSz;
        stkVal.push_back(1E18);
        stkSz.push_back(0);
        ll cans = 0;
        for (ll i = l[q]; i <= r[q]; i++) {
            ll sz = 1;
            while (ve[i] > stkVal.back()) {
                cans -= stkVal.back() * stkSz.back();
                sz += stkSz.back();
                stkVal.pop_back();
                stkSz.pop_back();
            }
            stkVal.push_back(ve[i]);
            stkSz.push_back(sz);
            cans += ve[i]*sz;
            lh[i] = cans;
        }}
        {vll stkVal;
        vll stkSz;
        stkVal.push_back(1E18);
        stkSz.push_back(0);
        ll cans = 0;
        for (ll i = r[q]; i >= l[q]; i--) {
            ll sz = 1;
            while (ve[i] > stkVal.back()) {
                cans -= stkVal.back() * stkSz.back();
                sz += stkSz.back();
                stkVal.pop_back();
                stkSz.pop_back();
            }
            stkVal.push_back(ve[i]);
            stkSz.push_back(sz);
            cans += ve[i]*sz;
            rh[i] = cans;
        }}
        ll qans = 1E18;
        for (ll i = l[q]; i <= r[q]; i++) {
            qans = min(qans, lh[i]+rh[i]-ve[i]);
        }
        ans[q] = qans;
    }
    return ans;
}

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