Submission #375470

#	Time	Username	Problem	Language	Result	Execution time	Memory
375470		wind_reaper	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	492 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

const int64_t INF = 1e18;

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<int64_t> 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), next.push_back(dt);
		N++;
	}
	n = N;

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

	int64_t inc = INF;
	for(int i = 0; i < 2*N; i++){
		for(int j = i+1; j < 2*N; j++){
			int64_t temp = 0;
			for(int k = 0; k < N; k++){
				if((v[k][0] <= next[i] && v[k][1] >= next[i]) || (v[k][0] <= next[j] && v[k][1] >= next[i]))
					continue;
				int64_t tmp = INF;
				if(next[i] < v[k][0])
					tmp = min(tmp, v[k][0] - next[i]);
				if(next[i] > v[k][1])
					tmp = min(tmp, next[i] - v[k][1]);
				if(next[j] < v[k][0])
					tmp = min(tmp, v[k][0] - next[j]);
				if(next[j] > v[k][1])
					tmp = min(tmp, next[j] - v[k][1]);
				
				temp += tmp;
			}
			inc = min(inc, temp);
		}
	}

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

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