# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
291637 | 2020-09-05T14:57:45 Z | crossing0ver | Discharging (NOI20_discharging) | C++17 | 0 ms | 0 KB |
#include<bits/stdc++.h> #define int long long #define ll long long #define fi first #define se second #define pii pair<int,int> #define vi vector<int> using namespace std; const int N = 1e6+6; //ll ans; int n,arr[N]; main() { int t = 10; cin >> n; int tot = n; for (int i = 1; i <= n; i++) { cin >> arr[i]; ll ans = 0; int mx = 0,k = 0,block = 0; for (int i = 1; i <= n; i++) { if (tot*mx <= block*arr[i]) { block = 0; k += arr[i]; tot = n - i+1; ans += k; } else { if (mx < arr[i]) { ans += (arr[i] - mx)*(block); k += arr[i] - mx; ans+=k; mx = arr[i]; } else ans += k; } mx = max(mx,arr[i]); block++; } cout << ans <<'\n'; }