Submission #44438

#	Time	Username	Problem	Language	Result	Execution time	Memory
44438		ssnsarang2023	Candies (JOI18_candies)	C++17	100 / 100	169 ms	10316 KiB

candies

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, int> pli;

const int N = (int)2e5+5;
const ll oo = (ll)1e16;
int n, nxt[N], pre[N];
ll a[N];
priority_queue<pli> pq;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
		nxt[i] = i + 1, pre[i] = i - 1;
		pq.push(pli(a[i], i));
	}
	nxt[n] = 0;
	ll ans = 0;
	for (int i = 1; i <= ((n + 1) >> 1); ++i) {
		for (; pq.top().first != a[pq.top().second]; pq.pop());
		int x = pq.top().second, l = pre[x], r = nxt[x];
		printf("%lld\n", ans += a[x]);
		pq.pop();
		pre[nxt[x] = nxt[r]] = x;
		nxt[pre[x] = pre[l]] = x;
		a[x] = l && r ? max(-oo, a[l] + a[r] - a[x]) : -oo;
		a[l] = a[r] = -oo;
		pq.push(pli(a[x], x));
	}
	return 0;
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
candies.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a[i]);
   ~~~~~^~~~~~~~~~~~~~~

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