Submission #102296

#	Time	Username	Problem	Language	Result	Execution time	Memory
102296		Nicholas_Patrick	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	69 ms	2032 KiB

bridge

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

int k, n;
vector <int> h, w, hw;
long long check(int i, int j){
	long long tot=0;
	for(int k = 0;k < n;k ++)
		tot+=min(abs(h[k]-hw[i])+abs(w[k]-hw[i]),abs(h[k]-hw[j])+abs(w[k]-hw[j]));
	return tot;
}
int main(){
	scanf("%d %d", &k, &n);
	bool cross;int s, t;
	long long tot1=0;
	char c;
	while(n--){
		while(true){
			c=getchar();
			if(c=='A'){
				cross=false;
				break;
			}else if(c=='B'){
				cross=true;
				break;
			}
		}
		scanf("%d", &s);
		while(true){
			c=getchar();
			if(c=='A'){
				break;
			}else if(c=='B'){
				cross^=true;
				break;
			}
		}
		scanf("%d", &t);
		if(cross){
			if(s>t)
				swap(s, t);
			h.push_back(s);
			w.push_back(t);
			hw.push_back(s);
			hw.push_back(t);
			tot1++;
		}else{
			tot1+=abs(t-s);
		}
	}
	n=h.size();
	sort(hw.begin(), hw.end());
	if(k==1){
		n=hw.size();
		long long tot2=0;
		k=n>>1;
		for(int i = 0;i < n;i ++)
			tot2+=abs(hw[k]-hw[i]);
		printf("%lld\n", tot1+tot2);
	}else if(k==2){
		long long tot2=200000000000000;
		long long curtot;
		for(int i = 0;i < n<<1;i ++){
			for(int j = 0;j < n<<1;j ++){
				curtot=check(i, j);
				tot2=min(tot2, curtot);
			}
		}
		printf("%lld\n", tot1+tot2);
	}
	return 0;
}
/*
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

*/

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &k, &n);
  ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &s);
   ~~~~~^~~~~~~~~~
bridge.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~

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