제출 #995481

#제출 시각아이디문제언어결과실행 시간메모리
995481Forested모임들 (IOI18_meetings)C++17
19 / 100
220 ms2136 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...