Submission #498709

#TimeUsernameProblemLanguageResultExecution timeMemory
498709jiahngDischarging (NOI20_discharging)C++14
47 / 100
894 ms1048580 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll typedef pair<int,int> pi; typedef vector <ll> vi; typedef vector <pi> vpi; typedef pair<pi, ll> pii; typedef set <ll> si; typedef long double ld; #define f first #define s second #define mp make_pair #define FOR(i,s,e) for(int i=s;i<=int(e);++i) #define DEC(i,s,e) for(int i=s;i>=int(e);--i) #define pb push_back #define all(x) (x).begin(), (x).end() #define lbd(x, y) lower_bound(all(x), y) #define ubd(x, y) upper_bound(all(x), y) #define aFOR(i,x) for (auto i: x) #define mem(x,i) memset(x,i,sizeof x) #define fast ios_base::sync_with_stdio(false),cin.tie(0) #define MOD 1000000007 #define maxn 1000010 #define INF (ll)1e18 int N; int dp[maxn], T[maxn]; int f(pi line, int x){ if (line == pi(-1,-1)) return INF; return line.f * x + line.s; } ld intersect(pi line1, pi line2){ return (line2.s - line1.s) / (line1.f - line2.f); } struct node{ int s,e,m; node *l,*r; pi val = pi(-1,-1); node (int ss,int ee){ s = ss; e = ee; m = (s + e) / 2; } void create_all(){ if (s != e){ l = new node(s,m); r = new node(m+1,e); l->create_all(); r->create_all(); } } void upd(pi line, node *prev){ val = prev->val; if (s == e){ if (f(line, s) < f(val, s)) val = line; return; } if (val == pi(-1,-1)){ val = line; l = prev->l; r = prev->r; }else if (intersect(line, val) < m){ if (f(line, m) < f(val, m)) swap(val, line); r = prev->r; l = new node(s,m); l->upd(line, prev->l); }else{ if (f(line, m) < f(val, m)) swap(val, line); l = prev->l; r = new node(m+1,e); r->upd(line, prev->r); } } int qry(int x){ if (s == e) return f(val, x); if (x > m) return min(f(val, x), r->qry(x)); else return min(f(val, x), l->qry(x)); } }; vector <node*> roots; int suffmax[maxn]; int32_t main(){ fast; cin >> N; FOR(i,1,N) cin >> T[i]; DEC(i,N,1) suffmax[i] = max(suffmax[i+1], T[i]); stack <pi> st; node *root = new node(1,N); root->create_all(); roots.pb(root); dp[N+1] = 0; DEC(i,N,1){ //~ int mx = -1; //~ dp[i] = INF; //~ FOR(k,i,N) { //~ mx = max(mx, T[k]); //~ if (k == N || T[k+1] > mx) dp[i] = min(dp[i], dp[k+1] + mx * (N - i + 1)); //~ } while (!st.empty() && st.top().f <= T[i]){ st.pop(); if (!st.empty()){ roots.pop_back(); } } if (!st.empty()){ node *newroot = new node(1,N); newroot->upd(pi(T[i],dp[st.top().s]), roots.back()); roots.pb(newroot); } st.push(pi(T[i], i)); dp[i] = suffmax[i] * (N - i + 1); if (!roots.empty()) dp[i] = min(dp[i], roots.back()->qry(N-i+1)); } //~ FOR(i,1,N) cout << dp[i] << ' '; //~ cout << '\n'; cout << dp[1]; }
#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...