oj.uz

답안 #685042

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
685042 2023-01-23T06:27:49 Z amunduzbaev 등산 경로 (IZhO12_route) C++17
100 / 100
 624 ms 60856 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef long long ll;
//~ #define int ll

const int N = 1e6 + 5;
const int MX = 2e9 + 5;
int a[N];

void usaco(string s){
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	//~ usaco("g");
	int n, k; cin >> n >> k;
	set<int> on;
	set<ar<int, 2>> mn;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	
	if(a[1] != a[n]) on.insert(1);
	for(int i=2;i<=n;i++){
		if(a[i] != a[i - 1]) on.insert(i);
	}
	
	auto to_l = [&](int i){
		//~ for(auto x : on) cout<<x<<" ";
		auto it = on.lower_bound(i);
		//~ cout<<": "<<i<<" "<<*it<<endl;
		assert(it != on.end() && *it == i);
		if(it == on.begin()) return *--on.end();
		return *--it;
	};
	auto to_r = [&](int i){
		auto it = on.upper_bound(i);
		if(it == on.end()) return *on.begin();
		return *it;
	};
	auto check = [&](int i){
		if(a[i] < a[to_l(i)] && a[i] < a[to_r(i)]){
			if(i < to_r(i)) mn.insert({to_r(i) - i, i});
			else mn.insert({n - i + to_r(i), i});
		}
	};
	for(auto i : on){
		check(i);
		assert(a[i] != a[to_l(i)] && a[i] != a[to_r(i)]);
	}
	
	ll res = 0;
	while(!mn.empty()){
		//~ for(auto x : on) cout<<a[x]<<" ";
		//~ cout<<"\n";
		auto w = (*mn.begin())[0], i = (*mn.begin())[1];
		int l = to_l(i), r = to_r(i);
		int h = min(a[l], a[r]) - a[i];
		//~ cout<<h<<" "<<w<<" "<<k<<"\n";
		if(h * 1ll * w > k){
			res += 2 * (k / w);
			a[i] += k / w;
			break;
		}
		res += 2 * h;
		a[i] += h; k -= h * w;
		mn.erase(mn.begin());
		//~ cout<<l<<" "<<r<<"\n";
		if(l == r) break;
		if(a[l] == a[i] && a[r] == a[i]){
			on.erase(i), on.erase(r);
			check(l);
		}
		else if(a[l] == a[i]){
			on.erase(i);
			check(l);
		}
		else if(a[r] == a[i]){
			on.erase(r);
			check(i);
		}
	}
	
	cout<<res<<"\n";
}

Compilation message

route.cpp: In function 'void usaco(std::string)':
route.cpp:13:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
route.cpp:14:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 50 ms 6176 KB Output is correct
11 Correct 62 ms 7880 KB Output is correct
12 Correct 29 ms 3916 KB Output is correct
13 Correct 617 ms 60856 KB Output is correct
14 Correct 617 ms 60684 KB Output is correct
15 Correct 615 ms 58700 KB Output is correct
16 Correct 615 ms 59760 KB Output is correct
17 Correct 623 ms 59768 KB Output is correct
18 Correct 617 ms 60524 KB Output is correct
19 Correct 624 ms 60752 KB Output is correct
20 Correct 322 ms 33560 KB Output is correct