Submission #1054455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054455		Adomas08	Palembang Bridges (APIO15_bridge)	C++14	31 / 100	2094 ms	3840 KiB

bridge

    #include <bits/stdc++.h>

    using namespace std;
    int k, n;

    int findmedian(vector<int> j){
    j.erase(remove(j.begin(), j.end(), -1), j.end());
    sort (j.begin(), j.end());
    if (j.size() == 0) return 0;
    return (j[j.size() / 2] + j[j.size() / 2 - 1]) / 2;
    }
    int main(){
    long long ans = 0;
    priority_queue <int> q;
    int k, n;
    cin >> k >> n;
    long long a[n*2];
    vector <int> v;
    char b[n], d[n];
    for (int i = 0; i < n; i++){
        cin >> b[i] >> a[i*2] >> d[i] >> a[i*2+1];
        if (b[i] == d[i]){
            v.push_back(-1);
            v.push_back(-1);
        }
        else {
            v.push_back(a[i*2]);
            v.push_back(a[i*2+1]);
        }
        if (a[i*2] > a[i*2+1]){
            int temp = a[i*2];
            a[i*2] = a[i*2+1];
            a[i*2+1] = temp;
        }
    }
    int f;
    if (k == 1){
    while (k--){
        f = findmedian(v);
        for (int i = 0; i < n; i++){
            if (f >= a[i*2] && f <= a[i*2+1]){
                v[i*2] = -1;
                v[i*2+1] = -1;
            }
        }
    }
    for (int i = 0; i < n; i++){
        if (b[i] == d[i]){
            ans += a[i*2+1] - a[i*2];
        }
        else{
            if (v[i*2] == -1){
                ans += a[i*2+1] - a[i*2] + 1;
            }
            else{
                if (f < a[i*2]) ans += 1 + a[i*2+1] - a[i*2] + 2 * (a[i*2] - f);
                if (f > a[i*2+1]) ans += 1 + a[i*2+1] - a[i*2] + 2 * (f - a[i*2+1]);
            }
        }
    }
    }
    else{
        ans = LLONG_MAX;
        for (int z = 0; z < 2 * n; z++){
        for (int y = 0; y < 2 * n; y++){
        long long curans = 0;
        int f = a[z];
        int g = a[y];
        vector <int> h = v;
        for (int i = 0; i < n; i++){
            if (f >= a[i*2] && f <= a[i*2+1]){
                h[i*2] = -1;
                h[i*2+1] = -1;
            }
        }
        for (int i = 0; i < n; i++){
            if (g >= a[i*2] && g <= a[i*2+1]){
                h[i*2] = -1;
                h[i*2+1] = -1;
            }
        }
        for (int i = 0; i < n; i++){
        if (b[i] == d[i]){
            curans += a[i*2+1] - a[i*2];
        }
        else{
            if (h[i*2] == -1){
                curans += a[i*2+1] - a[i*2] + 1;
            }
            else{
                long long c = LLONG_MAX;
                if (f < a[i*2])   c = min(1 + a[i*2+1] - a[i*2] + 2 * (a[i*2] - f), c);
                if (f > a[i*2+1]) c = min(1 + a[i*2+1] - a[i*2] + 2 * (f - a[i*2+1]), c);
                if (g < a[i*2])   c = min(1 + a[i*2+1] - a[i*2] + 2 * (a[i*2] - g), c);
                if (g > a[i*2+1]) c = min(1 + a[i*2+1] - a[i*2] + 2 * (g - a[i*2+1]), c);
                curans += c;
            }
        }
    }
    ans = min(curans, ans);
        }
    }
    }
    cout << ans;
    }

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