oj.uz

답안 #245420

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
245420 2020-07-06T11:39:25 Z arnold518 Candies (JOI18_candies) C++14
0 / 100
 8 ms 768 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const ll INF = 1e16;

int N;
ll A[MAXN+10], ans;

multiset<int> L, R;
multiset<pll, greater<pll>> S;

pii f(int x)
{
	int l, r;
	r=*R.lower_bound(x);
	l=*(--L.upper_bound(x));
	return {l, r};
}

int main()
{
    int i, j;

    scanf("%d", &N);
    for(i=1; i<=N; i++) scanf("%lld", &A[i]);
    for(i=0; i<=N+1; i++) L.insert(i), R.insert(i);
	for(i=1; i<=N; i++) S.insert({A[i], i});

	for(i=1; i<=(N+1)/2; i++)
	{
		ans+=S.begin()->first;
		printf("%lld\n", ans);
		int x=S.begin()->second;
		S.erase(S.begin());

		int l=f(x).first, r=f(x).second, pl=f(l-1).first, pr=f(l-1).second, ql=f(r+1).first, qr=f(r+1).second;

		L.erase(l), R.erase(r), S.erase({A[l], l});
		if(l!=1) L.erase(pl), R.erase(pr), S.erase({A[pl], pl});
		if(r!=N) L.erase(ql), R.erase(qr), S.erase({A[ql], ql});

		if(l!=1 && r!=N)
		{
			L.insert(pl); R.insert(qr);
			A[pl]=A[pl]+A[ql]-A[l];
			S.insert({A[pl], pl});
		}
	}
}

Compilation message

candies.cpp: In function 'int main()':
candies.cpp:27:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
candies.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
candies.cpp:30:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%lld", &A[i]);
                         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 768 KB Output isn't correct
2 Halted 0 ms 0 KB -