Submission #861706

#TimeUsernameProblemLanguageResultExecution timeMemory
861706wakandaaaDischarging (NOI20_discharging)C++17
100 / 100
108 ms26312 KiB
#include <bits/stdc++.h> #define int long long #define double long double using namespace std; #define mp make_pair #define fi first #define se second #define all(x) x.begin(), x.end() #define getbit(x, i) (((x) >> (i)) & 1) #define bit(x) (1 << (x)) #define popcount __builtin_popcountll mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count()); long long rand(long long l, long long r) { return l + rd() % (r - l + 1); } const int N = 1e6 + 5; const int mod = 1e9 + 7; // 998244353; const int lg = 25; // lg + 1 const int inf = 1e9; // INT_MAX; const long long llinf = 1e18; // LLONG_MAX; template<class X, class Y> bool minimize(X &a, Y b) { return a > b ? (a = b, true) : false; } template<class X, class Y> bool maximize(X &a, Y b) { return a < b ? (a = b, true) : false; } template<class X, class Y> bool add(X &a, Y b) { a += b; while (a >= mod) a -= mod; while (a < 0) a += mod; return true; } int n; int a[N]; int f[N]; double F(int j, int k) { return (f[j] - f[k]) / (j - k); } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; a[i] = max(a[i], a[i - 1]); } memset(f, 0, sizeof f); f[0] = 0; deque<int> q; q.push_back(0); for (int i = 1; i <= n; ++i) { while (q.size() >= 2 && F(q[0], q[1]) < a[i]) q.pop_front(); int j = q.front(); f[i] = a[i] * (n - j) + f[j]; while (q.size() >= 2 && F(q[q.size() - 2], q[q.size() - 1]) > F(q[q.size() - 1], i)) q.pop_back(); q.push_back(i); } cout << f[n]; return 0; } /* 5 1 3 2 6 3 27 7 1 1 2 2 2 2 2 14 */
#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...