Submission #44437

#	Time	Username	Problem	Language	Result	Execution time	Memory
44437		ssnsarang2023	Candies (JOI18_candies)	C++17	0 / 100	3 ms	504 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)1e18+7ll;
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));
	}
	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:21:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  for (int i = 1; i <= n + 1 >> 1; ++i) {
                       ~~^~~
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: 0 / 8
• Subtask 2: 0 / 92