Submission #102285

#	Time	Username	Problem	Language	Result	Execution time	Memory
102285		Nicholas_Patrick	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	66 ms	4412 KiB

bridge

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


int main(){
	int k, n;
	scanf("%d %d", &k, &n);
	vector <int> h, w, hw;
	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){
			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();
	if(k==1){
		sort(hw.begin(), hw.end());
		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;
		long long heretot;
		int i=0, j=1;
		reloop:
		for(;i < n<<1;i ++){
			curtot=0;
			for(int k = 0;k < n;k ++){
				curtot+=min(abs(h[k]-hw[i])+abs(w[k]-hw[i]), abs(h[k]-hw[j])+abs(w[k]-hw[j]));
				if(curtot>=tot2){
					i=n<<1;
					goto reloop;//exit
				}
			}
			tot2=min(tot2, curtot);
			while(true){
				j++;
				if(j==n<<1){
					i=n<<1;
					goto reloop;//exit
				}
				curtot=0;
				for(int k = 0;k < n;k ++){
					curtot+=min(abs(h[k]-hw[i])+abs(w[k]-hw[i]), abs(h[k]-hw[j])+abs(w[k]-hw[j]));
					if(curtot>tot2){
						j--;
						goto reloop;
					}
				}
				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:56:13: warning: unused variable 'heretot' [-Wunused-variable]
   long long heretot;
             ^~~~~~~
bridge.cpp:7: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:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &s);
   ~~~~~^~~~~~~~~~
bridge.cpp:33: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