This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 2e5 + 3;
const ll Log2 = 20;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;
ll n,a[N],prv[N],nxt[N],val[N];
void Link(ll x,ll y){
prv[y] = x; nxt[x] = y;
}
struct Node{
ll val,l,r;
};
bool operator < (Node a,Node b){
return a.val > b.val || (a.val == b.val && a.l > b.l) ||
(a.val == b.val && a.l > b.l && a.r > b.r);
}
set<Node> s;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);
#define task "test"
if (fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
//freopen(task".out", "w", stdout);
}
cin>>n;
for (ll i = 1;i <= n;i++) cin>>a[i],s.insert({a[i],i,i}),val[i] = a[i];
for (ll i = 1;i <= n;i++) Link(i - 1,i);
ll cur = 0,p;
for (ll i = 1;i <= (n + 1)/2;i++){
Node t = *s.begin(); s.erase(s.begin());
cur += t.val;
ll x = prv[t.l],y = nxt[t.r];
s.erase({val[x],x,t.l - 1}); s.erase({val[y],t.r + 1,y});
//cout<<val[x]<<" "<<x<<" "<<nxt[x]; return 0;
val[x] += val[y] - t.val; Link(x,y); s.insert({val[x],x,nxt[x]});
cout<<cur<<"\n";
}
}
Compilation message (stderr)
candies.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
1 | #pragma GCC optimization "O2"
|
candies.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
2 | #pragma GCC optimization "unroll-loop"
|
candies.cpp: In function 'int main()':
candies.cpp:43:16: warning: unused variable 'p' [-Wunused-variable]
43 | ll cur = 0,p;
| ^
candies.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |