제출 #713877

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
713877		PixelCat	Meetings (IOI18_meetings)	C++14	19 / 100	436 ms	1508 KiB

meetings

#ifdef NYAOWO
#include "grader.cpp"
#endif
#include "meetings.h"

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
using namespace std;
using LL = long long;
using pii = pair<LL, LL>;

const int MAXN = 5010;
const LL INF = 1e10;

int N, Q;
LL h[MAXN];
LL cl[MAXN], cr[MAXN];

LL query(int l, int r) {
    LL tot = 0;
    vector<pii> v;  // {index, value}
    v.eb(l - 1, INF);
    For(i, l, r) {
        while(v.back().S < h[i]) {
            auto p = v.back(); v.pop_back();
            tot -= p.S * (p.F - v.back().F);
        }
        tot += h[i] * (i - v.back().F);
        cl[i] = tot;
        v.eb(i, h[i]);
    }

    tot = 0;
    v.clear();
    v.eb(r + 1, INF);
    Forr(i, r, l) {
        while(v.back().S < h[i]) {
            auto p = v.back(); v.pop_back();
            tot -= p.S * (v.back().F - p.F);
        }
        tot += h[i] * (v.back().F - i);
        cr[i] = tot;
        v.eb(i, h[i]);
    }

    LL ans = cl[l] + cr[l] - h[l];
    For(i, l + 1, r) ans = min(ans, cl[i] + cr[i] - h[i]);
    return ans;
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
    N = sz(H);
    Q = sz(L);
    if(N <= 5000) {
        For(i, 0, N - 1) h[i] = H[i];
        vector<LL> C(Q);
        For(i, 0, Q - 1) {
            C[i] = query(L[i], R[i]);
        }
        return C;
    }
    std::vector<long long> C(Q);
    for (int j = 0; j < Q; ++j) {
        C[j] = H[L[j]];
    }
    return C;
}

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