제출 #139282

#제출 시각아이디문제언어결과실행 시간메모리
139282Nnandi모임들 (IOI18_meetings)C++14
19 / 100
5568 ms5292 KiB
#include "meetings.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 750005; vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) { int q = L.size(); vector<ll> ans(q); for(int j=0;j<q;j++) { ll a[maxn]; ll b[maxn]; stack<int> mp; for(int i=L[j];i<=R[j];i++) { while(!mp.empty() && H[mp.top()] < H[i]) { mp.pop(); } if(mp.empty()) { a[i] = (ll)(i - L[j] + 1) * (ll)H[i]; } else { a[i] = (ll)(i - mp.top()) * (ll)H[i] + a[mp.top()]; } mp.push(i); } while(!mp.empty()) { mp.pop(); } for(int i=R[j];i>=L[j];i--) { while(!mp.empty() && H[mp.top()] < H[i]) { mp.pop(); } if(mp.empty()) { b[i] = (ll)(R[j] - i + 1) * (ll)H[i]; } else { b[i] = (ll)(mp.top() - i) * (ll)H[i] + b[mp.top()]; } mp.push(i); } ans[j] = a[L[j]] + b[L[j]] - H[L[j]]; for(int i=L[j];i<=R[j];i++) { if(ans[j] > a[i] + b[i] - H[i]) { ans[j] = a[i] + b[i] - H[i]; } } } 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...