제출 #139253

#제출 시각아이디문제언어결과실행 시간메모리
139253fredbr모임들 (IOI18_meetings)C++17
0 / 100
5584 ms5864 KiB
#include "meetings.h" #include <bits/stdc++.h> using namespace std; using ll = long long; ll const inf = 0x3f3f3f3f3f3f3f3f; vector<ll> minimum_costs(vector<int> h, vector<int> L, vector<int> R) { int n = h.size(); vector<int> a(n), b(n); stack<int> pre; for (int i = 0; i < n; i++) { while (!pre.empty() and h[pre.top()] < h[i]) { b[pre.top()] = i; pre.pop(); } pre.push(i); } while (!pre.empty()) { b[pre.top()] = n; pre.pop(); } reverse(h.begin(), h.end()); for (int i = 0; i < n; i++) { while (!pre.empty() and h[pre.top()] < h[i]) { a[pre.top()] = i; pre.pop(); } pre.push(i); } while (!pre.empty()) { a[pre.top()] = n; pre.pop(); } reverse(h.begin(), h.end()); for (int& i : a) i = n-1-i; reverse(a.begin(), a.end()); int q = L.size(); vector<ll> res; for (int at = 0; at < q; at++) { ll ans = inf; int l = L[at], r = R[at]; vector<ll> resl(r-l+1); vector<ll> resr(r-l+1); for (int i = l; i <= r; i++) { if (a[i] < l) resl[i-l] = ll(h[i])*(i-l+1); else resl[i-l] = resl[a[i]-l] + (i-a[i])*h[i]; } for (int i = r; i >= l; i--) { if (b[i] > r) resr[i-l] = ll(h[i])*(r-i+1); else resr[i-l] = resr[b[i]-l] + (b[i]-i)*h[i]; } for (int i = l; i <= r; i++) { ans = min(ans, resl[i-l] + resr[i-l] - h[i]); } res.push_back(ans); } return res; }
#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...