Submission #691305

#TimeUsernameProblemLanguageResultExecution timeMemory
691305saayan007Discharging (NOI20_discharging)C++17
38 / 100
133 ms25516 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pi = pair<int, int>; using pl = pair<long long, long long>; using vi = vector<int>; using vl = vector<long long>; using vpi = vector<pair<int, int>>; using vpl = vector<pair<long long, long long>>; #define fur(i, a, b) for(ll i = a; i <= (ll)b; ++i) #define ruf(i, a, b) for(ll i = a; i >= (ll)b; --i) #define fr first #define sc second #define mp make_pair #define pb push_back #define eb emplace_back #define nl "\n" #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() const ll inf = 1e16L; struct CHT { struct Line { ll m, c; Line(ll a, ll b){ m = a; c = b; } ll isect(Line &other) { return (c - other.c + other.m - m + 1) / (other.m - m); } ll val(ll x) { return m*x + c; } }; deque<pair<Line, ll>> dq; void insert(ll m, ll c) { Line nex(m, c); if(dq.empty()) { dq.eb(nex, 0); return; } while(!dq.empty()) { Line pr = dq.back().fr; ll x = dq.back().sc; if(nex.m == pr.m) { if(nex.c > pr.c) { return; } } else if(nex.isect(pr) > x) { break; } dq.pop_back(); } if(dq.empty()) { dq.eb(nex, 0); return; } dq.eb(nex, nex.isect(dq.back().fr)); } ll query(ll x) { ll m = dq.size(); while(m > 1 && dq[1].sc <= x) { dq.pop_front(); --m; } return dq.front().fr.val(x); } }; int main() { ios::sync_with_stdio(0); cin.tie(0); ll n; cin >> n; ll t[n + 1]; fur(i, 1, n) cin >> t[i]; CHT cht; ll dp[n + 1]; dp[0] = 0; fur(i, 1, n) { cht.insert(n - i + 1, dp[i - 1]); dp[i] = cht.query(t[i]); } cout << dp[n] << nl; }
#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...