#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define N +100500
#define MaxS N * N
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
//#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;
vector <ll> Sum[2];
vector <ll> Kol[2], Vec[2], SVec[2];
ll s[2];
ll nn[2];
ll h[N], ans, i, n, mid, l, r;
void leftupdkol(ll v, ll value) {for (v++; v < sz(Kol[0]); v += v & -v) Kol[0][v] += value;}
void rightupdkol(ll v, ll value) {for (v++; v < sz(Kol[1]); v += v & -v) Kol[1][v] += value;}
void leftupdsum(ll v, ll value) {for (v++; v < sz(Sum[0]); v += v & -v) Sum[0][v] += value;}
void rightupdsum(ll v, ll value) {for (v++; v < sz(Sum[1]); v += v & -v) Sum[1][v] += value;}
ll getleftkol(ll v){ll res = 0; for (v++; v > 0; v -= v & -v) res += Kol[0][v];return res;}
ll getrightkol(ll v){ll res = 0; for (v++; v > 0; v -= v & -v) res += Kol[1][v];return res;}
ll getleftsum(ll v){ll res = 0; for (v++; v > 0; v -= v & -v) res += Sum[0][v];return res;}
ll getrightsum(ll v){ll res = 0; for (v++; v > 0; v -= v & -v) res += Sum[1][v];return res;}
ll getleftind(ll x) {return (upper_bound(SVec[0].begin(), SVec[0].end(), x) - SVec[0].begin()) - 1;}
ll getrightind(ll x) {return (upper_bound(SVec[1].begin(), SVec[1].end(), x) - SVec[1].begin()) - 1;}
void addleft(ll v)
{
ll u = getleftind(Vec[0][v]);
leftupdkol(u, 1);
leftupdsum(u, Vec[0][v]);
nn[0]++;
s[0] += Vec[0][v];
}
void addright(ll v)
{
ll u = getrightind(Vec[1][v]);
// cerr << v << el;
rightupdkol(u, 1);
rightupdsum(u, Vec[1][v]);
nn[1]++;
s[1] += Vec[1][v];
}
void removeleft(ll v)
{
ll u = getleftind(Vec[0][v]);
leftupdkol(u, -1);
leftupdsum(u, -Vec[0][v]);
nn[0]--;
s[0] -= Vec[0][v];
}
void removeright(ll v)
{
ll u = getrightind(Vec[1][v]);
rightupdkol(u, -1);
rightupdsum(u, -Vec[1][v]);
nn[1]--;
s[1] -= Vec[1][v];
}
ll leftF(ll v)
{
ll u = getleftind(v);
if (u < 0) return s[0] - nn[0] * 1ll * v;
ll le = getleftkol(u);
ll ri = nn[0] - le;
ll leftsum = getleftsum(u);
// cerr << s[0] << " " << nn[0] << " " << le << " " << leftsum << el;
ll rightsum = s[0] - leftsum;
return le * v - leftsum + rightsum - ri * v;
}
ll rightF(ll v)
{
ll u = getrightind(v);
if (u < 0) return s[1] - nn[1] * 1ll * v;
ll le = getrightkol(u);
ll ri = nn[1] - le;
ll leftsum = getrightsum(u);
// cerr << s[1] << " " << nn[1] << " " << le << " " << leftsum << el;
ll rightsum = s[1] - leftsum;
return le * v - leftsum + rightsum - ri * v;
}
int main()
{
srand(time(0));
ios_base::sync_with_stdio(0);
iostream::sync_with_stdio(0);
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
// in("input.txt");
// out("output.txt");
cin >> n;
for (i = 0; i < n; i++) cin >> h[i];
ans = 1e18;
for (i = 0; i < n; i++) Vec[0].pb(h[i] - i), Vec[1].pb(h[i] + i);
SVec[0] = Vec[0];
SVec[1] = Vec[1];
sort(SVec[0].begin(), SVec[0].end());
sort(SVec[1].begin(), SVec[1].end());
Sum[0].assign(n + 10, 0);
Sum[1].assign(n + 10, 0);
Kol[0].assign(n + 10, 0);
Kol[1].assign(n + 10, 0);
for (i = 0; i < n; i++) addright(i);
for (mid = 0; mid < n; mid++)
{
addleft(mid);
removeright(mid);
l = max(mid + 1, n - mid);
r = 2e9;
while (r - l > 10)
{
ll m1 = (l + r) / 2ll, m2 = m1 + 1;
ll f1 = leftF(m1 - mid) + rightF(m1 + mid);
ll f2 = leftF(m2 - mid) + rightF(m2 + mid);
if (f1 <= f2) r = m1;
else l = m2;
}
for (; l <= r; l++)
{
// cerr << mid << " " << l << " " << leftF(l - mid) + rightF(l + mid) << el;
ans = min(ans, leftF(l - mid) + rightF(l + mid));
}
}
cout << ans;
}
// x ^ 2 + y ^ 2 = 1
// x * a_i + y * b_i
// a_i = -b_i * tan(alpha)
// a_i / -b_i = tan(alpha)
// alpha = atan(a_i / (-b_i))
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
384 KB |
Output is correct |
| 2 |
Correct |
10 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
512 KB |
Output is correct |
| 2 |
Correct |
10 ms |
512 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
512 KB |
Output is correct |
| 2 |
Correct |
13 ms |
512 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
640 KB |
Output is correct |
| 2 |
Correct |
17 ms |
608 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
19 ms |
640 KB |
Output is correct |
| 2 |
Correct |
20 ms |
512 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
31 ms |
888 KB |
Output is correct |
| 2 |
Correct |
31 ms |
768 KB |
Output is correct |
| 3 |
Correct |
17 ms |
512 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
180 ms |
2300 KB |
Output is correct |
| 2 |
Correct |
178 ms |
2428 KB |
Output is correct |
| 3 |
Correct |
174 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
218 ms |
2812 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
298 ms |
3572 KB |
Output is correct |
| 2 |
Correct |
317 ms |
3956 KB |
Output is correct |
| 3 |
Correct |
243 ms |
3700 KB |
Output is correct |
| 4 |
Correct |
232 ms |
3816 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
562 ms |
6368 KB |
Output is correct |
| 2 |
Correct |
450 ms |
6508 KB |
Output is correct |
| 3 |
Correct |
267 ms |
3316 KB |
Output is correct |
| 4 |
Correct |
574 ms |
6500 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
667 ms |
8792 KB |
Output is correct |
| 2 |
Correct |
693 ms |
8640 KB |
Output is correct |
| 3 |
Correct |
559 ms |
6372 KB |
Output is correct |
| 4 |
Correct |
777 ms |
8036 KB |
Output is correct |
| 5 |
Correct |
156 ms |
2428 KB |
Output is correct |
