Submission #45012

#	Time	Username	Problem	Language	Result	Execution time	Memory
45012		RezwanArefin01	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	2 ms	876 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[]) {
	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()); 
	pos.erase(unique(pos.begin(), pos.end()), pos.end());
	if(k == 1) {
		int sz = pos.size(); 
		ll mn = get(pos[sz / 2]);
		if(sz / 2 + 1 < sz) mn = min(mn, get(pos[sz / 2 + 1])); 
		printf("%lld\n", mn + pre);
	} else {
		ll ans = 1e18;
		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:33:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < pos.size(); i++) {
                  ~~^~~~~~~~~~~~
bridge.cpp:34:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = i + 1; j < pos.size(); j++) {
                       ~~^~~~~~~~~~~~
bridge.cpp:16: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:20: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: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37