제출 #337615

#제출 시각아이디문제언어결과실행 시간메모리
337615ncduy0303Discharging (NOI20_discharging)C++17
100 / 100
129 ms12000 KiB
#include <bits/stdc++.h> using namespace std; #define ar array #define ll long long const int MAX_N = 1e5 + 1; const ll MOD = 1e9 + 7; const ll INF = 1e9; struct convexhull { struct line { ll m, c; line(ll m, ll c): m(m), c(c) {} ll operator()(ll x) {return m * x + c;} }; deque<line> dq; bool bad(line a, line b, line c) { return 1.0 * (c.c - a.c) / (a.m - c.m) <= 1.0 * (b.c - a.c) / (a.m - b.m); } void add(line l) { while(dq.size() > 1 && bad(dq[(int)dq.size() - 2], dq.back(), l)) dq.pop_back(); dq.emplace_back(l); } ll query(ll x) { // min query, increasing x while (dq.size() >= 2 && dq[0](x) >= dq[1](x)) dq.pop_front(); return dq[0](x); } // ll query(ll x) { // min query, any x // int lo = -1, hi = dq.size() - 1; // while (lo + 1 < hi) { // int mid = (lo + hi) / 2; // if (dq[mid](x) >= dq[mid + 1](x)) lo = mid; // else hi = mid; // } // return dq[hi](x); // } }; // struct convexhull { // struct line { // ll m, c; // line(ll m, ll c): m(m), c(c) {} // ll operator()(ll x) {return m * x + c;} // }; // deque<line> dq; // bool check(line p1, line p2, line p3) { // return (p2.m - p1.m) * (p3.c - p2.c) >= (p3.m - p2.m) * (p2.c - p1.c); // } // void add(line y) { // decreasing slope // while (dq.size() >= 2 && check(dq[dq.size() - 2], dq[dq.size() - 1], y)) dq.pop_back(); // dq.push_back(y); // } // ll query(ll x) { // min query, increasing x // while (dq.size() >= 2 && dq[0](x) >= dq[1](x)) dq.pop_front(); // return dq[0](x); // } // ll query(ll x) { // min query, any x // int lo = -1, hi = dq.size() - 1; // while (lo + 1 < hi) { // int mid = (lo + hi) / 2; // if (dq[mid](x) >= dq[mid + 1](x)) lo = mid; // else hi = mid; // } // return dq[hi](x); // } // }; void solve() { int n; cin >> n; vector<int> a(n + 1); for (int i = n; i > 0; i--) cin >> a[i]; vector<int> st; for (int i = 1; i <= n; i++) { while (st.size() && a[st.back()] <= a[i]) st.pop_back(); st.push_back(i); } int m = st.size(); vector<ll> dp(m + 1); convexhull cht; for (int i = 1; i <= m; i++) { cht.add({a[st[i - 1]], dp[i - 1]}); dp[i] = cht.query(st[i - 1]); } cout << dp[m] << "\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tc = 1; // cin >> tc; for (int t = 1; t <= tc; t++) { // cout << "Case #" << t << ": "; solve(); } }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...