Submission #23774

#	Time	Username	Problem	Language	Result	Execution time	Memory
23774		rubabredwan	Palembang Bridges (APIO15_bridge)	C++14	17 / 100	2000 ms	3776 KiB

bridge

/*  Bismillahir Rahmanir Rahim  */

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;
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;
	for(int i = 1; i <= n; ++i){
		for(int a = 0; a <= 1; a++){
	        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]);
                ans += aa;
            }
            ret = min(ret, ans);
        }
	}
	cout << ret << 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;
}

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