| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 485750 | 5enpa1 | Safety (NOI18_safety) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int __int128
#define vec vector
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define sq(x) (x)*(x)
#define fast_io ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef pair<int,int> PII;
int f(int k, int b, int x){
return k*x+b;
}
int k, x, b, y, sum;
long long n, h, ans;
signed main(){
#ifdef LOCAL
ifstream cin("input.txt");
ofstream cout("output.txt");
#endif
fast_io;
cin >> n >> h;
vec < long long > q(n);
vec < int > w;
for(auto &i: q) cin >> i, sum += i;
multiset < int > one;
multiset < int > two;
int left = 0;
int right = 0;
for(int i = 0; i < n; ++i){
one.insert(q[i]-left);
one.insert(q[i]-left);
while(sz(one) > sz(two)){
auto it = one.end();
it--;
int adder = *it;
adder -= right;
adder += left;
two.insert(adder);
one.erase(one.find(*it));
}
auto it = one.end();
it--;
while((*it)+left > (*two.begin())+right){
two.insert(*it+left-right);
one.erase(it);
one.insert(*two.begin()+right-left);
two.erase(two.begin());
it = one.end();
it--;
}
left -= h;
right += h;
}
left += h;
right -= h;
vec < int > fin;
for(auto &i: one) fin.pb(i+left);
for(auto &i: two) fin.pb(i+right);
b = -sum;
for(int i = 0; i < n; ++i)
b -= i*h;
k = n;
ans = 1e18;
for(int i = sz(fin)-1; i >= 0; --i){
x = fin[i];
y = k*x+b;
ans = min(ans, y);
k--;
b += x;
}
cout << ans;
return 0;
}