Submission #23776

#	Time	Username	Problem	Language	Result	Execution time	Memory
23776		rubabredwan	Palembang Bridges (APIO15_bridge)	C++14	9 / 100	33 ms	2020 KiB

bridge

/*  Bismillahir Rahmanir Rahim  */

#include <bits/stdc++.h>

using namespace std;

const int N = 105;
const long long oo = 1e18;

int k, n; 
long long pos[N][2];
char fk[N][2];

void solve_big(){
    long long ret = oo;
    for(int i = 1; i <= n; i++){
        for(int a = 0; a <= 1; a++){
            for(int j = 1; j <= n; j++){
                for(int b = 0; b <= 1; b++){
                    long long ans = 0;
                    for(int f = 1; f <= n; f++){
                        if(fk[f][0] == fk[f][1]){
                            ans += abs(pos[f][1] - pos[f][0]);
                            continue;
                        }
                        long long aa = 1LL + abs(pos[f][0] - pos[i][a]) + abs(pos[f][1] - pos[i][a]);
                        long long bb = 1LL + abs(pos[f][0] - pos[j][b]) + abs(pos[f][1] - pos[j][b]);
                        ans += min(aa, bb);
                    }
                    ret = min(ret, ans);
                }
            }
        }
    }
    cout << ret << endl;
}

void solve_small(){
	long long ret = oo;
	long long add = 0;
	long long pre = 0;
	long long suf = 0;
	vector<long long> gg;
	for(int i = 1; i <= n; ++i){
		if(fk[i][0] == fk[i][1]) add += abs(pos[i][1] - pos[i][0]);
		else{
			gg.push_back(pos[i][0]);
			gg.push_back(pos[i][1]);
			suf += pos[i][0];
			suf += pos[i][1];
			add += 1LL;
		}
	}
	sort(gg.begin(), gg.end());
    if(gg.size() == 0) ret = 0;
	for(long long i = 0; i < gg.size(); ++i){
		long long ans = 0;
		ans += (gg[i] * i) - pre;
		ans += suf - (gg[i] * 1LL * (gg.size() - i));
		pre += gg[i];
		suf -= gg[i];
		ret = min(ret, ans);
	}
	cout << ret + add << endl;
}

int main(){
    cin >> k >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= 1; j++){
            cin >> fk[i][j] >> pos[i][j];
        }
    }
    if(k == 1) solve_small();
    else solve_big();
    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'void solve_small()':
bridge.cpp:56:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(long long i = 0; i < gg.size(); ++i){
                         ^

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