제출 #1113687

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1113687		Tsagana	등산 경로 (IZhO12_route)	C++14	0 / 100	1 ms	336 KiB

route

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define lnl long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

int a[1000001];
map<int, int> mp;
map<int, int> ms;
map<int, int> mb;
pq<int> q;

void solve () {
	int n, k; cin >> n >> k;
	int calc = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		if (i > 1) calc += abs(a[i] - a[i-1]);
		if (mp.find(a[i]) == mp.end()) {
			q.push(-a[i]);
			ms[a[i]] = a[i];
		}
		mp[a[i]]++;
	}
	calc += abs(a[n] - a[1]);
	int mn;
	while (1) {
		int x = -q.top(); q.pop();
		if (q.empty()) {
			mn = -1;
			break ;
		}
		int y = mp[x];
		int z = -q.top();

		if (k < y) {
			mn = x;
			break ;
		}
		
		if (k >= y * (z - x)) {
			k -= y * (z - x);
			ms[x] = z;
			mb[x] = 1;
			mp[z] += mp[x];
			continue ;
		}
		if (k >= y) {
			int l = k / y;
			ms[x] = x + l;
			mb[x] = 1;
			mn = x + l;
			k -= y * l;
			break ;
		}
		mn = x;
		break ;
	}

	for (int i = 1; i <= n; i++) {
		while (mb[a[i]]) a[i] = ms[a[i]];
		if (a[i] == mn && k) {a[i]++; k--;}
	}
	
	int ans = 0;
	for (int i = 2; i <= n; i++) {
		ans += abs(a[i] - a[i-1]);
	}
	cout << calc - (ans + abs(a[n] - a[1]));
}
int main() {IOS solve(); return 0;}

• Subtask 1: 0 / 100