제출 #1069954

#제출 시각아이디문제언어결과실행 시간메모리
1069954Joshua_Andersson모임들 (IOI18_meetings)C++14
19 / 100
5550 ms7260 KiB
#include "meetings.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll linf = ll(1e18); typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> p2; #define rep(i, high) for (int i = 0; i < high; i++) #define repp(i, low, high) for (int i = low; i < high; i++) #define repe(i, container) for (auto& i : container) #define sz(container) ((int)container.size()) #define all(x) begin(x),end(x) #if _LOCAL #define assert(x) if (!(x)) __debugbreak() #endif typedef vector<ll> vll; struct node { int best, l, r; int mid; node *lc, *rc; }; vll h; int n; node* build_tree(int l, int r) { return 0; } ll solve(int l, int r) { if (l > r) return 0; if (l==r) { return h[l]; } ll largest = 0; repp(i, l, r + 1) largest = max(largest, h[i]); ll ret = (r - l + 1) * largest; vll lindex; repp(i, l, r + 1) if (h[i] == largest) lindex.push_back(i); lindex.insert(lindex.begin(), l - 1); lindex.push_back(r + 1); ll tot_len = r - l + 1; repp(i, 1, sz(lindex)) { ll interval_len = (lindex[i]-1) - (lindex[i - 1]+1) + 1; ret = min(ret, (tot_len - interval_len) * largest + solve(lindex[i - 1] + 1, lindex[i] - 1)); } return ret; } vll minimum_costs(vi H, std::vector<int> L, std::vector<int> R) { h = vll(H.begin(), H.end()); n = sz(h); build_tree(0, n - 1); int q = sz(L); vll ret(q); rep(qu, q) { int l = L[qu]; int r = R[qu]; ret[qu] = solve(l, r); } return ret; }
#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...