제출 #674659

#제출 시각아이디문제언어결과실행 시간메모리
674659QwertyPiDischarging (NOI20_discharging)C++14
100 / 100
145 ms22608 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 1e6 + 11; int a[N], dp[N]; int m[N], c[N], l, r; int floor_div(int a, int b){ return a / b - (a % b != 0 && a < 0); } int interX(int m1, int c1, int m2, int c2){ return floor_div(c2 - c1, m1 - m2); } void add(int _m, int _c){ while(r - l >= 2 && interX(m[r - 2], c[r - 2], _m, _c) <= interX(m[r - 2], c[r - 2], m[r - 1], c[r - 1])) r--; m[r] = _m, c[r] = _c; r++; } int qry(int x){ while(r - l >= 2 && m[l] * x + c[l] >= m[l + 1] * x + c[l + 1]) l++; return m[l] * x + c[l]; } int32_t main(){ cin.tie(0); cout.tie(0)->sync_with_stdio(false); int n; cin >> n; for(int i = 0; i < n; i++) cin >> a[i]; for(int i = 1; i < n; i++) a[i] = max(a[i - 1], a[i]); memset(dp, 0x3f, sizeof(dp)); dp[0] = 0; for(int i = 0; i < n; i++){ add(-i, dp[i]); dp[i + 1] = a[i] * n + qry(a[i]); } cout << dp[n] << endl; }
#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...