답안 #37848

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
37848 2017-12-28T10:25:37 Z 14kg 등산 경로 (IZhO12_route) C++11
100 / 100
216 ms 23792 KB
#include <stdio.h>
#include <set>
#include <queue>
#include <vector>
#include <functional>
#include <algorithm>
#define N 1000001
#define next(x) (x==n?1:x+1)
#define before(x) (x==1?n:x-1)
#define min2(x,y) (x<y?x:y)

using namespace std;
typedef pair<int, pair<int, int> > pip;
int n, m, in[N], S_sum;
bool cc[N];
pair<int, int> go1[N], go2[N];
//priority_queue<pip, vector<pip>, greater<pip> > Q;
set<pip> S;

void S_push(pip x) {
	set<pip>::iterator it;
	S.insert(x), S_sum += x.first;
	while (S.begin() != S.end() && S_sum > m) {
		it = S.end(), it--, S_sum -= it->first;
		S.erase(it);
	}
}

int main() {
	int s, num = -1;
	int path, x, y, len, tot = 0, tx, ty;
	bool check;
	pip temp;

//	freopen("input.txt", "r", stdin);

	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &in[i]);
		if (num < in[i]) num = in[i], s = i;
	}

	path = s, len = 0, check = false;;
	for (int i = next(s); i != s; i = next(i)) {
		if (in[path] > in[i]) x = i, len = 1, check = true;
		if (in[path] == in[i]) len++;
		if (in[path] < in[i] && check) {
			S_push({ len,{ x, path } }), check = false;
			go1[path] = { x,len - 1 }, go2[x] = { path,len - 1 };
		} path = i;
	}
	if (in[path] < in[s] && check) {
		S_push({ len,{ x, path } });
		go1[path] = { x,len - 1 }, go2[x] = { path,len - 1 };
	}

	while (S.end() != S.begin()) {
	//	if(m%10000==0)printf("%d \n", m);
		temp = *S.begin(), S.erase(S.begin());
		if (m < temp.first) break;
		len = temp.first, x = temp.second.first, y = temp.second.second;
		
		num = min2(min2(in[before(x)] - in[x], in[next(y)] - in[y]), m / len);
		tot += num, m -= len*num, S_sum -= len*num;

		in[x]+=num;
		if (x != y) in[y] += num;

		tx = x, num = 0, path = len;
		while (in[before(tx)] == in[tx]) {
			num++, len++, tx = before(tx);
			if (go1[tx].second) len += go1[tx].second, tx = go1[tx].first;
			if (num > n) break;
		}
		go1[x] = { tx,len - path };
		if (in[before(tx)] == in[tx]) break;
		if (in[before(tx)] < in[tx]) continue;

		ty = y, path = len;
		while (in[ty] == in[next(ty)]) {
			len++, ty = next(ty);
			if (go2[ty].second) len += go2[ty].second, ty = go2[ty].first;
		}
		go2[y] = { ty,len - path };

		if (in[ty] < in[next(ty)]) {
			S_push({ len,{ tx,ty } });
			go1[ty] = { tx,len - 1 }, go2[tx] = { ty,len - 1 };
		}
	} printf("%d", tot * 2);
	// getchar(), getchar();
}

Compilation message

route.cpp: In function 'int main()':
route.cpp:37:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
route.cpp:39:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &in[i]);
                      ^
route.cpp:52:21: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if (in[path] < in[s] && check) {
                     ^
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 21680 KB Output is correct
2 Correct 0 ms 21680 KB Output is correct
3 Correct 0 ms 21680 KB Output is correct
4 Correct 0 ms 21680 KB Output is correct
5 Correct 0 ms 21680 KB Output is correct
6 Correct 0 ms 21680 KB Output is correct
7 Correct 0 ms 21680 KB Output is correct
8 Correct 0 ms 21680 KB Output is correct
9 Correct 0 ms 21680 KB Output is correct
10 Correct 23 ms 21680 KB Output is correct
11 Correct 19 ms 23792 KB Output is correct
12 Correct 13 ms 21680 KB Output is correct
13 Correct 189 ms 21680 KB Output is correct
14 Correct 216 ms 21680 KB Output is correct
15 Correct 159 ms 21680 KB Output is correct
16 Correct 149 ms 21680 KB Output is correct
17 Correct 176 ms 21680 KB Output is correct
18 Correct 159 ms 21680 KB Output is correct
19 Correct 169 ms 21680 KB Output is correct
20 Correct 166 ms 21680 KB Output is correct