Submission #375450

#	Time	Username	Problem	Language	Result	Execution time	Memory
375450		wind_reaper	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	68 ms	5340 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

int32_t main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	
	int k, n;
	cin >> k >> n;

	int N = 0;
	int64_t ans = 0;
	
	vector<array<int, 2>> v;	
	vector<array<int, 2>> next;
	for(int i = 0; i < n; i++){
		char s, d;
		int st, dt;
		cin >> s >> st >> d >> dt;
		ans += int64_t(abs(dt - st));
		if(s == d)
			continue;
		if(st > dt) swap(st, dt);
		v.push_back({st, dt});
		next.push_back({st, 0}), next.push_back({dt, 1});
		N++;
	}
	n = N;

	sort(v.begin(), v.end());
	sort(next.begin(), next.end());

	int current = -1;
	array<int, 2> a = {n, 0};
	int64_t inc = 0;
	for(int i = 0; i < n; i++){
		inc += 2LL*int64_t(v[i][0] - current);
	}
	int64_t cur = inc;
	for(int i = 0; i < 2*n; i++){
		int nxt = next[i][0];
		cur = cur - 2LL*a[0]*int64_t(nxt - current) - 2LL*a[1]*int64_t(nxt - current);
		inc = min(inc, cur);
		current = nxt;
		a[next[i][1]]--;
	}

	cout << ans + inc + n << '\n';
	return 0; 
}

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