Submission #914919

#	Time	Username	Problem	Language	Result	Execution time	Memory
914919		tvladm2009	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	600 KiB

bridge

#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
 
using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double; 
const string FILENAME = "input";

int k, n;

struct kek {
	char p;
	int s;
	char q;
	int t;
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//read(FILENAME);
	cin >> k >> n;
	ll add = 0;
	vector<kek> v;
	vector<pair<int, bool>> points;
	for (int i = 1; i <= n; i++) {
		char p, q;
		int s, t;
		cin >> p >> s >> q >> t;
		if (p == q) {
			add += abs(s - t);
		} else {
			points.pb(mp(s, (s > t)));
			points.pb(mp(t, (t > s)));
			v.pb({p, s, q, t});
		}
	}
	if (k == 1) {
		sort(all(points));
		ll sumR = 0, cntR = 0;
		ll sumL = 0, cntL = 0;
		for (auto i: points) {
			sumR += i.first;
			cntR++;
		}	
		int in = 0;
		ll res = 1e18;
		for (auto bridge: points) {
			cntL++;
			cntR--;
			sumL += bridge.first;
			sumR -= bridge.first;
			ll cost = cntL * bridge.first - sumL + sumR - cntR * bridge.first;
			cost += v.size();
			chkmin(res, cost);
		}
		cout << res + add << '\n';
	}
	return 0;
}
/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

5
2
5
5
7
*/

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:81:7: warning: unused variable 'in' [-Wunused-variable]
   81 |   int in = 0;
      |       ^~

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