이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int Q = L.size();
vector<ll> ans(Q);
for(int q=0; q<Q; q++){
int l = L[q], r = R[q]+1;
int sz = r-l;
vector<ll> pref(sz), suff(sz);
stack<pair<ll,ll>> s;
ll curr = 0;
for(int i=l; i<r; i++){
ll rm = 0;
while(s.size() and s.top().first <= H[i]){
rm += s.top().second;
curr -= s.top().first*s.top().second;
s.pop();
}
s.push({H[i], rm+1});
curr += H[i]*(rm+1);
pref[i-l] = curr;
}
while(s.size()) s.pop();
curr = 0;
for(int i=r-1; i>=l; i--){
ll rm = 0;
while(s.size() and s.top().first <= H[i]){
rm += s.top().second;
curr -= s.top().first*s.top().second;
s.pop();
}
s.push({H[i], rm+1});
curr += H[i]*(rm+1);
suff[i-l] = curr;
}
ll mn = min(pref[sz-1], suff[0]);
for(int i=1; i<sz; i++){
mn = min(mn, pref[i-1]+suff[i]);
}
ans[q] = mn;
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |