Submission #1042864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042864		kaopj	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	2080 ms	600 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,b;
    int mx=0,r=0;
    for (int i=0;i<n;i++) {
        int p;
        char c;
        cin >> c >> p;
        mx=max(mx,p);
        a.push_back({p,c-'A'});
        cin >> c >> p;
        mx=max(mx,p);
        if (a.back().s == c-'A') {
            r+=abs(p-a.back().f);
            a.pop_back();
        } else b.push_back({p,c-'A'});
    }
    int ans=1e18,cur;
    n=a.size();
    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 << r+ans;
}

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