oj.uz

답안 #58149

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
58149 2018-07-17T04:24:01 Z khsoo01 Candies (JOI18_candies) C++11
0 / 100
 8 ms 652 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

const ll N = 200005, inf = 1e18;

ll n, a[N], par[N];

set<pll> val, idx;

ll Find (ll X) {
	if(par[X] == X) return X;
	return par[X] = Find(par[X]);
}

int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++) {
		scanf("%lld",&a[i]);
		par[i] = i;
		val.insert({-a[i], i});
		idx.insert({i, -a[i]});
	}
	ll R = 0;
	for(ll i=1;i<=(n+1)/2;i++) {
		ll A, B, C, D;
		tie(A, B) = *val.begin();
		val.erase(pll(A, B));
		idx.erase(pll(B, A));
		R -= A;
		A *= -1;
		if(B != 1) {
			tie(C, D) = *idx.lower_bound(pll(Find(B-1), -inf));
			idx.erase(pll(C, D));
			val.erase(pll(D, C));
			A += D;
			par[B] = B-1;
		}
		if(B != n) {
			tie(C, D) = *idx.lower_bound(pll(B+1, -inf));
			idx.erase(pll(C, D));
			val.erase(pll(D, C));
			A += D;
			par[B+1] = B;
		}
		B = Find(B);
		val.insert(pll(A, B));
		idx.insert(pll(B, A));
		printf("%lld\n",R);
	}
}

Compilation message

candies.cpp: In function 'int main()':
candies.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
candies.cpp:21: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.0

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

Subtask #2
0 / 92.0

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