Submission #1288182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288182		gustavo_d	Palembang Bridges (APIO15_bridge)	C++20	0 / 100	7 ms	584 KiB

bridge

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1e5;
const int INF = 1e9;
const ll INFLL = 1e18;

int k, n;

int a[MAXN], b[MAXN];

ll ans = INFLL;

vector<int> bridges;
void solve() {
    ll res = 0;
    for (int i=0; i<n; i++) {
        int d = INF;
        for (int bridge : bridges) {
            d = min(d, abs(a[i] - bridge) + 1 + abs(b[i] - bridge));
        }
        res += d;
    }
    ans = min(ans, res);
}

void rec(int toPut, int i) {
    if (toPut == 0) {
        solve();
        return;
    }
    for (int j=i; j<2*n; j++) {
        bridges.push_back((j < n ? a[j] : b[j]));
        rec(toPut - 1, j+1);
        bridges.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin >> k >> n;
    ll base = 0;
    for (int i=0; i<n; i++) {
        char side1, side2;
        cin >> side1 >> a[i] >> side2 >> b[i];
        if (side1 == side2) {
            base += abs(b[i] - a[i]);
            n--; i--;
            continue;
        }
        if (a[i] > b[i]) swap(a[i], b[i]);
    }
    k = min(k, n);
    rec(k, 0);
    cout << base + ans << '\n';

    return 0;
}

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