oj.uz

Submission #49865

# Submission time Handle Problem Language Result Execution time Memory
49865 2018-06-04T01:09:29 Z MatheusLealV Candies (JOI18_candies) C++17
0 / 100
 3 ms 504 KB 
#include <bits/stdc++.h>
#define N 200050
#define f first
#define s second
using namespace std;
#define int long long
typedef pair<int, int> pii;

int n, v[N], ans;

set < pii > pq, list;

struct linked_list
{
	int esq[N], dir[N];

	void clear()
	{
		memset(esq, 0, sizeof esq);

		memset(dir, 0, sizeof dir);
	}

	void erase(int p)
	{
		dir[esq[p]] = dir[p];

		esq[dir[p]] = esq[p];
	}
} L;

int32_t main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n;

	for(int i = 1; i <= n; i++)
	{
		cin>>v[i];

		L.esq[i] = i - 1;

		L.dir[i] = i + 1;

		pq.insert({-v[i], i});
	}

	for(int i = 1; i <= ((n + 1)/2); i++)
	{
		auto it = pq.begin();

		int x = -(*it).f, id = (*it).s;

		int l = L.esq[id], r = L.dir[id];

		L.erase(l), L.erase(r);

		int novo = -v[id] + v[l] + v[r];

		pq.erase({-x, id}), pq.erase({-v[l], l}), pq.erase({-v[r], r});

		pq.insert({-novo, id});

		ans += x;

		v[id] = novo;

		cout<<ans<<"\n";
	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -