// Make the best become better
// No room for laziness
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n;
int a[maxN];
set<int> pos;
struct cmp
{
bool operator () (int i, int j) const
{
return (a[i] > a[j] || (a[i] == a[j] && i < j));
}
};
multiset<int, cmp> S;
void ReadInput()
{
cin >> n;
for(int i=1; i<=n; i++)
{
cin >> a[i];
S.insert(i);
pos.insert(i);
}
}
void Solve()
{
int res = 0;
for(int i=1; i<=(n+1)/2; i++)
{
auto it = S.begin();
res += a[*it];
auto it1 = pos.find(*it);
auto l = it1, r = it1;
int val = -a[*it];
if(l != pos.begin())
{
l--;
val += a[*l];
S.erase(*l);
pos.erase(*l);
}
r++;
if(r != pos.end())
{
val += a[*r];
S.erase(*r);
pos.erase(*r);
}
int tmp = *it;
S.erase(tmp);
a[tmp] = val;
S.insert(tmp);
cout << res << '\n';
}
}
int32_t main()
{
// freopen("x.inp", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ReadInput();
Solve();
}
/*
49
98
143
187
225
252
262
267
269
269
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
