답안 #100670

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
100670 2019-03-13T06:32:33 Z cki86201 등산 경로 (IZhO12_route) C++11
100 / 100
310 ms 29544 KB
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

int N, K;
int A[1000010];
int p[1000010]; int Find(int x) { return p[x] == x ? x : p[x] = Find(p[x]); }
int li[1000010], ri[1000010], z[1000010];
priority_queue <pii, vector<pii>, greater<pii> > pq;
inline int nxt_i(int i) { return i==N-1 ? 0 : i+1; }
inline int pre_i(int i) { return i==0 ? N-1 : i-1; }

int main() {
	scanf("%d%d", &N, &K);
	rep(i, N) scanf("%d", A + i);
	rep(i, N) li[i] = pre_i(i), ri[i] = nxt_i(i);
	rep(i, N) p[i] = i, z[i] = 1;
	rep(i, N) {
		int j = nxt_i(i);
		if(A[i] != A[j]) continue;
		int pi = Find(i), pj = Find(j);
		if(pi != pj) {
			p[pi] = pj; li[pj] = li[pi];
			z[pj] += z[pi];
		}
	}
	rep(i, N) if(p[i] == i) {
		if(A[i] < A[li[i]] && A[i] < A[ri[i]]) pq.push(pii(z[i], i));
	}
	ll ans = 0;
	while(!pq.empty()) {
		pii t = pq.top(); pq.pop();
		int x = t.Se;
		int mul = min(A[Find(li[x])], A[Find(ri[x])]) - A[x];
		if((ll)mul * t.Fi >= K) {
			ans += 2 * (K / t.Fi);
			break;
		}
		ans += 2 * mul;
		K -= t.Fi * mul;
		A[x] += mul;
		if(A[x] == A[Find(li[x])]) {
			int pi = Find(li[x]), pj = Find(x);
			if(pi != pj) {
				p[pi] = pj; li[pj] = li[pi];
				z[pj] += z[pi];
			}
		}
		if(A[x] == A[Find(ri[x])]) {
			int pi = Find(x), pj = Find(ri[x]);
			if(pi != pj) {
				p[pi] = pj; li[pj] = li[pi];
				z[pj] += z[pi];
			}
		}
		x = Find(x);
		if(A[x] < A[Find(li[x])] && A[x] < A[Find(ri[x])]) pq.push(pii(z[x], x));
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

route.cpp: In function 'int main()':
route.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~
route.cpp:42:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  rep(i, N) scanf("%d", A + i);
            ~~~~~^~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 432 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 23 ms 3160 KB Output is correct
11 Correct 28 ms 4084 KB Output is correct
12 Correct 21 ms 4020 KB Output is correct
13 Correct 186 ms 29432 KB Output is correct
14 Correct 310 ms 29544 KB Output is correct
15 Correct 227 ms 27552 KB Output is correct
16 Correct 153 ms 28536 KB Output is correct
17 Correct 147 ms 28536 KB Output is correct
18 Correct 177 ms 29356 KB Output is correct
19 Correct 184 ms 29432 KB Output is correct
20 Correct 136 ms 25848 KB Output is correct