Submission #45014

#	Time	Username	Problem	Language	Result	Execution time	Memory
45014		RezwanArefin01	Palembang Bridges (APIO15_bridge)	C++17	31 / 100	2061 ms	2440 KiB

bridge

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

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

typedef long long ll;
typedef pair<int, int> ii; 

vector<int> pos; vector<ii> v;
ll get(int x) { ll ret = 0;
	for(ii a : v) ret += abs(a.first - x) + abs(a.second - x) + 1; 
	return ret;
}
int main(int argc, char const *argv[]) {
#ifdef LOCAL_TESTING
	freopen("in", "r", stdin);
#endif
	int n, k; scanf("%d %d", &k, &n); 
	ll pre = 0; 
	for(int i = 0; i < n; i++) {
		char p, q; int s, t;
		scanf(" %c %d %c %d", &p, &s, &q, &t);
		if(p == q) pre += abs(s - t); 
		else v.emplace_back(s, t), pos.push_back(s), pos.push_back(t); 
	}
	sort(pos.begin(), pos.end()); 
	if(k == 1) {
		int sz = pos.size(); ll mn = 0;
		if(v.size()) {
			mn = get(pos[sz / 2]);
			if(sz / 2 + 1 < sz) mn = min(mn, get(pos[sz / 2 + 1])); 
		} printf("%lld\n", mn + pre);
	} else {
		pos.erase(unique(pos.begin(), pos.end()), pos.end());
		ll ans = 1e18;
		if(!pos.size()) ans = 0; else
		for(int i = 0; i < pos.size(); i++) {
			for(int j = i + 1; j < pos.size(); j++) {
				ll tot = 0;
				int x = pos[i], y = pos[j]; 
				for(ii a : v) {
					tot += min(abs(a.first - x) + abs(a.second - x),
							   abs(a.first - y) + abs(a.second - y)) + 1;
				} ans = min(ans, tot);
			}
		} printf("%lld\n", ans + pre);
	}
}

Compilation message (stderr)

bridge.cpp: In function 'int main(int, const char**)':
bridge.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < pos.size(); i++) {
                  ~~^~~~~~~~~~~~
bridge.cpp:39:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = i + 1; j < pos.size(); j++) {
                       ~~^~~~~~~~~~~~
bridge.cpp:19:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, k; scanf("%d %d", &k, &n); 
            ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %d %c %d", &p, &s, &q, &t);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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