제출 #1156450

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156450		bobo	모임들 (IOI18_meetings)	C++20	19 / 100	5589 ms	5240 KiB

meetings

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

#define int long long

std::vector<int> minimum_costs(std::vector<int32_t> H, std::vector<int32_t> l,
                                     std::vector<int32_t> r) {
    int n = H.size();
    vector<int> h(n+1);
    for (int i = 1; i <= n; i++) h[i] = H[i-1];
    int q = l.size();
    vector<int> o;
    for (int i = 0; i < q; i++) {
        vector<int> pre(n+1, 0);
        stack<array<int, 3>> st;
        l[i]++, r[i]++;
        for (int j = l[i]; j <= r[i]; j++) {
            int lm = j;
            pre[j] = pre[j - 1];
            while (!st.empty() && h[j] >= st.top()[2]) {
                pre[j] -= (st.top()[1] - st.top()[0] + 1) * (st.top()[2]);
                lm = st.top()[0], st.pop();
            }
            pre[j] += (j - lm + 1) * h[j];
            st.push({lm, j, h[j]});
        }
        vector<int> suf(n+2, 0);
        while (!st.empty()) st.pop();
        for (int j = r[i]; j >= l[i]; j--) {
            int lm = j;
            suf[j] = suf[j + 1];
            while (!st.empty() && h[j] >= st.top()[2]) {
                suf[j] -= (st.top()[1] - st.top()[0] + 1) * (st.top()[2]);
                lm = st.top()[1], st.pop();
            }
            suf[j] += (lm - j + 1) * h[j];
            st.push({j, lm, h[j]});
        }
        int ans = 1e18;
        for (int j = l[i]; j <= r[i]; j++) {
            // cout << l[i] << " " << r[i] << " " << j << " " << pre[j] << " " << suf[j] << " " << pre[j] + suf[j] << '\n';
            ans = min(ans, pre[j] + suf[j] - h[j]);
        }
        o.push_back(ans);
    }
    return o;
}

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