제출 #1361141

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

meetings

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

using ll = long long;

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    int N = (int)H.size();
    int Q = (int)L.size();

    vector<ll> A(N);
    for (int i = 0; i < N; i++) A[i] = H[i];

    vector<ll> LC((long long)N * N, 0);

    for (int l = 0; l < N; l++) {
        vector<int> st;

        for (int i = l; i < N; i++) {
            while (!st.empty() && A[st.back()] < A[i]) st.pop_back();

            int p = st.empty() ? l - 1 : st.back();

            LC[(long long)l * N + i] =
                (ll)(i - p) * A[i] + (p >= l ? LC[(long long)l * N + p] : 0);

            st.push_back(i);
        }
    }
    vector<vector<int>> byR(N);
    for (int q = 0; q < Q; q++) {
        byR[R[q]].push_back(q);
    }

    vector<ll> ans(Q);
    vector<ll> RC(N, 0);

    for (int r = 0; r < N; r++) {
        vector<int> st;

        for (int i = r; i >= 0; i--) {
            while (!st.empty() && A[st.back()] < A[i]) st.pop_back();

            int p = st.empty() ? r + 1 : st.back();

            RC[i] = (ll)(p - i) * A[i] + (p <= r ? RC[p] : 0);

            st.push_back(i);
        }

        for (int q : byR[r]) {
            int l = L[q];
            ll best = LLONG_MAX;

            for (int i = l; i <= r; i++) {
                ll cur = LC[(long long)l * N + i] + RC[i] - A[i];
                best = min(best, cur);
            }

            ans[q] = best;
        }
    }

    return ans;
}

• 서브태스크 1: 4 / 4
• 서브태스크 2: 15 / 15
• 서브태스크 3: 0 / 17
• 서브태스크 4: 0 / 24
• 서브태스크 5: 0 / 40