Submission #41500

#	Time	Username	Problem	Language	Result	Execution time	Memory
41500		RockyB	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	2055 ms	4048 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=100000, maxx=1000000001;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef pair<ll,pi> pii;
typedef vector<pi> vii;

#define fi first
#define sc second
#define mp make_pair
#define pb push_back

ll k,n;
string buf,bufx;
ll x, y;
vi dict;
ll sum[2*maxn+10];
ll gege;

int main(){
	ios_base::sync_with_stdio(false);
	gege=0;

	cin >> k >> n;
	if (k==1){
		for(int i=0;i<n;i++){
			cin >> buf >> x >> bufx >> y;
			if (buf==bufx) {
				gege+= labs(x-y);
			}
			else {
				dict.pb(x); dict.pb(y);
			}
		}

		sort(dict.begin(),dict.end());
		for(int i=0;i<dict.size();i++){
			sum[i]=(i==0?0:sum[i-1])+dict[i];
		}

		ll ans = LONG_LONG_MAX;

		for(int i=0;i<dict.size();i++){
			ans =min(ans,dict[i]*(i+1)-sum[i]+sum[dict.size()-1]-sum[i]-dict[i]*(ll(dict.size())-i-1));
			//cout << dict[i] <<" " << dict[i]*(i+1)-sum[i]+sum[dict.size()-1]-sum[i]-dict[i]*(ll(dict.size())-i-1) << "\n";
		}
		if (ans==LONG_LONG_MAX) ans=0;
		cout << ans+gege+dict.size()/2 << "\n";
		return 0;
	}
	else{
		vii dic;
		for(int i=0;i<n;i++){
			cin >> buf >> x >> bufx >> y;
			if (buf==bufx){
				gege+=labs(x-y);
			}
			else{
				dic.pb(mp(x,y));
				dict.pb(x); dict.pb(y);
			}
		}

		sort(dict.begin(),dict.end());
		ll ans = LONG_LONG_MAX, semen;

		for(int i=0;i<dict.size();i++){
			ll l = 0, r = 1000000001;
			ll mid1,mid2,mid3,semen1,semen2,semen3;
			while(l<r){
				mid1=l+(r-l)/3; mid2=(l+(r-l)*2/3); mid3 = (l+r)/2;
				
				semen1=0,semen2=0,semen3=0;
				for(int k=0;k<dic.size();k++){
					semen1+=min(labs(dic[k].fi-dict[i])+labs(dic[k].sc-dict[i]),labs(dic[k].fi-mid1)+labs(dic[k].sc-mid1));
					semen2+=min(labs(dic[k].fi-dict[i])+labs(dic[k].sc-dict[i]),labs(dic[k].fi-mid2)+labs(dic[k].sc-mid2));		
					semen3+=min(labs(dic[k].fi-dict[i])+labs(dic[k].sc-dict[i]),labs(dic[k].fi-mid3)+labs(dic[k].sc-mid3));		
				}
				if (semen1>semen3&&semen2>semen3){
					l=mid1; r=mid2;
				}
				else if (semen1>semen3&&semen2<semen3){
					l=mid1;
				}
				else{
					r=mid2;
				}
			
				ans = min(ans,min(semen1,min(semen3,semen2)));
		//		cout << dict[l] << " " << dict[r]<<"\n";
			//	cout << l << " dan " << r << " jadinya " << ans << "\n";
			
			}
			semen = 0;
			for(int k=0;k<dic.size();k++){
					semen+=min(labs(dic[k].fi-dict[i])+labs(dic[k].sc-dict[i]),labs(dic[k].fi-l)+labs(dic[k].sc-l));
			}
			ans=min(semen,ans);
		}
		if (ans==LONG_LONG_MAX) ans=0;
		cout << ans + gege+dict.size()/2 << "\n";
	}
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:39:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<dict.size();i++){
                ^
bridge.cpp:45:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<dict.size();i++){
                ^
bridge.cpp:69:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<dict.size();i++){
                ^
bridge.cpp:76:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=0;k<dic.size();k++){
                  ^
bridge.cpp:97:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0;k<dic.size();k++){
                 ^

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