Submission #656597

#	Time	Username	Problem	Language	Result	Execution time	Memory
656597		haojiandan	Candies (JOI18_candies)	C++14	0 / 100	1 ms	340 KiB

candies

// wygzgyw
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
	if (t<0) { putchar('-'); write(-t); return; }
	if (t>9) write(t/10);
	putchar('0'+t%10);
}
template <typename T> void writeln(T t) { write(t); puts(""); }
#define MP make_pair
typedef long long ll;
const int maxn=(2e5)+10;
int n,a[maxn];
bool vis[maxn];
ll val[maxn];
priority_queue<pair<ll,int> > q;
int nxt[maxn],pre[maxn];
void link(int x,int y) {
	if (x) nxt[x]=y;
	if (y) pre[y]=x;
}
int main() {
	read(n);
	for (int i=1;i<=n;i++) read(a[i]),pre[i]=i-1,nxt[i]=(i==n?0:i+1),q.push(MP(a[i],i)),val[i]=a[i];
	ll ans=0;
	for (int i=1;i<=(n+1)/2;i++) {
		pair<ll,int> A=q.top(); q.pop();
		int x=A.second;
		if (vis[x]) { i--; continue; }
		ans+=A.first; printf("%lld\n",ans);
		int y=pre[x],z=nxt[x];
		val[x]=val[y]+val[z]-val[x];
		vis[y]=vis[z]=1;
		link(x,nxt[z]),link(pre[y],x);
		if (y&&z) q.push(MP(val[x],x));
	}
	return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 92