제출 #558979

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
558979		hhhhaura	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	274 ms	15168 KiB

bridge

#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i --)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))
#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)
using namespace std;
#ifdef wiwihorz
#define print(a...)cerr<<"Line "<<__LINE__<<":",kout("["+string(#a)+"] = ", a)
void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
void kout() { cerr << endl; }
template<class T1,class ... T2>void kout(T1 a,T2 ... e){cerr<<a<<" ",kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
#define x first
#define y second
namespace solver1 {
	int n, k, ans;
	vector<pii> v;
	vector<int> a;
	void init_(int _n, int _k) {
		ans = 0;
		n = _n, k = _k;
		assert(k == 1);
		v.clear();
	}
	void solve() {
		n = signed(v.size());
		rep(i, 0, n - 1) {
			a.push_back(v[i].x);
			a.push_back(v[i].y);
		}
		sort(all(a));
		int mid = a[(n * 2 - 1) / 2];
		for(auto i : a) ans += abs(mid - i);
		cout << ans + n << "\n";

	}

};
namespace solver2 {
	int n, k, ans, sa, sb;
	vector<pii> v;
	vector<int> L, R;
	multiset<int> a, b;
	void init_(int _n, int _k) {
		ans = 0, sa = 0, sb = 0;
		n = _n, k = _k;
		assert(k == 2);
	}
	void insert(int x) {
		if(!a.size()) {
			a.insert(x);
			sa += x;
		}
		else {
			if(x <= *a.rbegin()) {
				a.insert(x);
				sa += x;
			}
			else {
				b.insert(x);
				sb += x;
			}
			if(a.size() > b.size() + 1) {
				auto it = prev(a.end());
				sa -= *it, sb += *it;
				b.insert(*it);
				a.erase(it);
			}
			if(b.size() > a.size()) {
				auto it = b.begin();
				sb -= *it, sa += *it;
				a.insert(*it);
				b.erase(it);
			}
		}
	}
	void solve() {
		n = v.size();
		L.assign(n, 0);
		R.assign(n, 0);
		sa = 0, sb = 0;
		sort(all(v), [&](pii a, pii b){
			return a.x + a.y < b.x + b.y;
		});
		rep(i, 0, n - 1) {
			insert(v[i].x);
			insert(v[i].y);
			L[i] = sb - sa;
		}
		sa = 0, sb = 0;
		a.clear();
		b.clear();
		rrep(i, 0, n - 1) {
			insert(v[i].x);
			insert(v[i].y);
			R[i] = sb - sa;
		}
		int best = INF;
		rep(i, 0, n) {
			int val = 0;
			if(i - 1 >= 0) val += L[i - 1];
			if(i < n) val += R[i];
			best = min(best, val);
		}
		cout << ans + best + n << "\n";
	}
};
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int k, n;
	cin >> k >> n;
	if(k == 1) {
		using namespace solver1;
		init_(n, k);
		rep(i, 1, n) {
			char x, y;
			int a, b;
			cin >> x >> a;
			cin >> y >> b;
			if(x == y) ans += abs(a - b);
			else v.push_back({a, b});
		}
		solve();
	}
	else {
		using namespace solver2;
		init_(n, k);
		rep(i, 1, n) {
			char x, y;
			int a, b;
			cin >> x >> a;
			cin >> y >> b;
			if(x == y) ans += abs(a - b);
			else v.push_back({a, b});
		}
		solve();
	
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    5 | #pragma loop-opt(on)
      | 
bridge.cpp:20:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |             ^~~~
bridge.cpp:20:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |                    ^~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37