제출 #853073

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
853073		aymanrs	Palembang Bridges (APIO15_bridge)	C++14	41 / 100	2049 ms	5164 KiB

bridge

#include<bits/stdc++.h>
using namespace std;
void solve(){
	int k, n, a, b;cin >> k >> n;
	char c,h;
	long long sl = 0, ans = LONG_LONG_MAX, cur = 0, tans = 0;
	vector<pair<int, int>> e;
	for(int i = 0;i < n;i++){
		cin >> c >> a >> h >> b;
		if(a>b)swap(a,b);
		tans += b-a;
		if(c==h) continue;
		tans++;
		e.emplace_back(a, -i-1);
		e.emplace_back(b, i+1);
	}
	if(e.empty()){
		cout << tans << '\n';
		return;
	}
	sort(e.begin(), e.end());
	int pr = e[0].first;
	for(auto p : e){
		cur += sl*(p.first-pr);
		pr = p.first;
		if(p.second > 0) sl += 2;
		vector<pair<int, int>> g;
		int v[n+1];fill(v, v+n+1, -1);
		long long slope = 0, CUR = 0;
		for(auto pp : e){
			if(pp.first <= p.first) continue;
			if(pp.second < 0){
				CUR += 2*(pp.first-p.first);
				slope -= 2;
				g.emplace_back(pp.first, 2);
				v[-pp.second] = pp.first-p.first;
			} else if(v[pp.second] != -1){
				g.emplace_back(pp.first, 2);
				g.emplace_back(pp.first+v[pp.second], -2);
			}
		}
		if(g.empty()){
			ans = min(ans, cur);
			continue;
		}
		sort(g.begin(), g.end());
		int pre = p.first;
		for(auto pp : g){
			CUR += slope*(pp.first-pre);
			pre = pp.first;
			ans = min(ans, cur+CUR);
			slope += pp.second;
		}
	}
	cout << ans+tans << '\n';
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

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