Submission #602892

#	Time	Username	Problem	Language	Result	Execution time	Memory
602892		fuad27	Palembang Bridges (APIO15_bridge)	C++17	31 / 100	2079 ms	2536 KiB

bridge

/*
 * Created: 2022-07-23 16:00
*/
#ifndef LOCAL
	#pragma GCC optimize("O3,unroll-loops")
	#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) FOR(i,0,b)
#define FORN(i,a,b) for(int i=int(b)-1;i>=a;i--)
#define per(i,b) FORN(i,0,b)

#define mkp make_pair
#define pb push_back
#define ep emplace_back
#define ff first
#define ss second
#define bg begin()
#define ed end()
#define sz(x) (int)x.size()
#define all(x) (x).bg,(x).ed
#define FIO ios_base::sync_with_stdio(0);\
	cin.tie(0);

template<class t> using vc=vector<t>;;
template<class t> using vvc=vc<vc<t>>;

using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi= vc<int>;
using vll= vc<ll>;


#ifdef LOCAL
#include "/home/fuad/cp/dbg.h"
#else
#define dbg(x...)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rngll(chrono::steady_clock::now().time_since_epoch().count());

void solve() {
	int n, k;
	cin >> k >> n;
	if(k == 1) {
		vc<ll> v;
		ll ans=0;
		rep(i,n) {
			char a, b;
			int c, d;
			cin >> a >> c >> b >> d;
			if(a == b) {
				ans+=abs(c-d);
			}
			else {
				v.pb(c);
				v.pb(d);
			}
		}
		sort(all(v));
		int mid = v[v.size()/2];
		for(int i:v) {
			ans+=abs(i-mid);
		}
		cout << ans +v.size()/2<< "\n";
	}
	else {
		vc<ll> v;
		ll ans=0;
		vc<pll> vv;
		rep(i,n) {
			char a, b;
			int c, d;
			cin >> a >> c >> b >> d;
			if(a == b) {
				ans+=abs(c-d);
			}
			else {
				v.pb(c);
				v.pb(d);
				vv.pb(mkp(c,d));
			}
		}
		sort(all(v));
		ll ans2=1e18;
		if(v.size() == 0)ans2=0;
		for(int i:v) {
			for(int j:v) {
				ll res=0;
				for(auto c:vv) {
					res+=min(abs(c.ff-i)+abs(c.ss-i), abs(c.ff-j)+abs(c.ss-j))+1;
				}
				ans2=min(ans2,res);
			}
		}
		cout<<ans+ans2<<"\n";
	}
}

int main () {
	FIO;
	int t=1;
	// cin >> t;
	while(t--)
		solve();
}

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