Submission #995481

#	Time	Username	Problem	Language	Result	Execution time	Memory
995481		Forested	Meetings (IOI18_meetings)	C++17	19 / 100	220 ms	2136 KiB

meetings

#include <bits/stdc++.h>
using namespace std;
using i32 = int;
using i64 = long long;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = V<V<T>>;
#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, l, r) for (i32 i = (i32)(l); i < (i32)(r); ++i)
#define PER2(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
#define PER3(i, l, r) for (i32 i = (i32)(r) - 1; i >= (i32)(l); --i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER(...) OVERRIDE4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define LEN(x) (i32)size(x)
#define ALL(x) begin(x), end(x)
template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

#include "meetings.h"

constexpr i32 INF = 1001001001;
constexpr i64 INF64 = 3003003003003003003;

i64 solve_naive(V<i32> h) {
    i32 n = LEN(h);
    V<i64> cost(n, 0);
    V<pair<i64, i32>> stc;
    stc.emplace_back(INF, -1);
    i64 cur = 0;
    REP(i, n) {
        while (stc.back().first <= h[i]) {
            i64 v;
            i32 j;
            tie(v, j) = stc.back();
            stc.pop_back();
            cur -= v * (j - stc.back().second);
        }
        cur += (i64)h[i] * (i - stc.back().second);
        stc.emplace_back(h[i], i);
        cost[i] += cur;
    }
    stc.clear();
    stc.emplace_back(INF, n);
    cur = 0;
    PER(i, n) {
        while (stc.back().first <= h[i]) {
            i64 v;
            i32 j;
            tie(v, j) = stc.back();
            stc.pop_back();
            cur -= v * (stc.back().second - j);
        }
        cur += (i64)h[i] * (stc.back().second - i);
        stc.emplace_back(h[i], i);
        cost[i] += cur;
    }
    REP(i, n) {
        cost[i] -= h[i];
    }
    i64 mn = INF64;
    REP(i, n) {
        chmin(mn, cost[i]);
    }
    return mn;
}

V<i64> minimum_costs(V<i32> h, V<i32> l, V<i32> r) {
    i32 n = LEN(h);
    i32 q = LEN(l);
    assert(n <= 5000 && q <= 5000);
    V<i64> ans(q);
    REP(i, q) {
        ans[i] = solve_naive(V<i32>(h.begin() + l[i], h.begin() + r[i] + 1));
    }
    return ans;
}

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