Submission #1042860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042860		kaopj	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	2066 ms	432 KiB

bridge

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
#define int long long
#define lgm cin.tie(0)->sync_with_stdio(0);
#define be(x) x.begin(),x.end()
#define v vector
#define f first
#define s second
const int mod = 1e9+7;
signed main() {
    lgm;
    int n,k;
    cin >> k>>n;
    v<pair<int,int>> a(n),b(n);
    int mx=0;
    for (int i=0;i<n;i++) {
        int p;
        char c;
        cin >> c >> p;
        mx=max(mx,p);
        a[i]={p,c-'A'};
        cin >> c >> p;
        mx=max(mx,p);
        b[i]={p,c-'A'};
    }
    int ans=1e9,cur;
    if (k == 1) {
        for (int i=0;i<mx;i++) {
            cur=0;
            for (int j=0;j<n;j++) {
                if (a[j].s==b[j].s) {
                    cur+=abs(a[j].f-b[j].f);
                } else {
                    cur+=1+abs(a[j].f-i)+abs(b[j].f-i);
                }
            }
            ans=min(ans,cur);
        }
    } else {
        for (int i=0;i<mx;i++) {
            for (int j=i+1;j<mx;j++) {
                cur=0;
                for (int k=0;k<n;k++) {
                    if (a[k].s==b[k].s) {
                        cur+=abs(a[k].f-b[k].f);
                    } else {
                        cur+=1+min(abs(a[k].f-i)+abs(b[k].f-i),abs(a[k].f-j)+abs(b[k].f-j));
                    }
                }
                ans=min(ans,cur);
            }
        }
    }
    cout << ans;
}

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