Submission #660028

#	Time	Username	Problem	Language	Result	Execution time	Memory
660028		aebov	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	41 ms	1492 KiB

bridge

#include<iostream>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<map>
#include<utility>
#include<unordered_map>
#include<vector>
#include<set>
#define pii pair<int,int>
#define pll pair<ll, ll>
#define F first
#define S second
#define ll long long
#define pb push_back
using namespace std;

const int N = (int)1e5 + 5, mod = (ll)1e9 + 7;
int n, k, x, y;
char ch, hc;
ll sm = 0, sm2 = (ll)1e18 + 18;
vector<int> cv;
bool cmp(int i,int j){
  return cv[i] < cv[j];
}
void sub(){
//	cerr << "\n entered #sub 2 \n";
	vector<pii> vc; vc.pb({0,0});
	for(int i = 1; i <= n; i ++){
		cin >> ch >> x >> hc >> y;
		if(ch == hc) sm += abs(x - y);
		else vc.pb({min(y,x), max(x,y)});
	} n = vc.size() - 1;
//	cout << "N " << n << endl;
	for(int i = 1; i <= n; i ++) {
		cv.pb(vc[i].F);
		cv.pb(vc[i].S);
	}
	sort(cv.begin(), cv.end(), cmp);
  	//exit(0);
//	for(auto u : cv)cout << u << endl;
	for(int i = 0; i < cv.size(); i ++){
		for(int j = i; j < cv.size(); j ++) {
			int x = cv[i], y = cv[j];
			ll sum = 0;
			for(int z = 1; z <= n; z ++){
				if(vc[z].S < x) sum +=  (x<<1) - vc[z].F - vc[z].S + 1;
				else if(vc[z].F > y) sum += vc[z].F + vc[z].S - (y<<1) + 1;
				else if(x < vc[z].F && vc[z].S < y)sum += min(vc[z].F + vc[z].S -(x<<1) + 1,(y<<1) - vc[z].F - vc[z].S + 1);
				else sum += vc[z].S - vc[z].F + 1;
			}
			sm2 = min(sm2, sum);
		}
	}
//	cout << sm  << " " << sm2 << endl;
	cout << sm + sm2 << endl;
	exit(0);
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> k >> n;
	vector<int> vc;
	if(k == 2 && n < 101)sub();
//	cerr << "\n enteres #sub1 \n";
	for(int i = 1; i <= n; i ++){
		cin >> ch >> x >> hc >> y;
		if(ch == hc) sm += abs(x - y);
		else sm ++, vc.pb(x), vc.pb(y);
	}
	sort(vc.begin(), vc.end());
	int pos = vc[(vc.size() - 1) / 2];
	for(auto x : vc)sm += abs(x - pos);
	cout << sm << endl;
}

Compilation message (stderr)

bridge.cpp: In function 'void sub()':
bridge.cpp:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for(int i = 0; i < cv.size(); i ++){
      |                 ~~^~~~~~~~~~~
bridge.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(int j = i; j < cv.size(); j ++) {
      |                  ~~^~~~~~~~~~~

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