Submission #1110880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110880		vladilius	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	37 ms	3548 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
#define pb push_back
#define ff first
#define ss second
const ll inf = numeric_limits<ll> :: max();

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int k, n; cin>>k>>n;
    vector<pii> all;
    ll out = 0;
    while (n--){
        char t1, t2; int x1, y1; cin>>t1>>x1>>t2>>y1;
        if (t1 == t2){
            out += abs(x1 - y1);
            continue;
        }
        if (x1 > y1) swap(x1, y1);
        all.pb({x1, y1});
    }
    
    n = (int) all.size();
    vector<int> imp;
    for (int i = 0; i < n; i++){
        imp.pb(all[i].ff); imp.pb(all[i].ss);
    }

    ll mn = inf;
    if (k == 1){
        if (!all.empty()){
            vector<int> f;
            for (auto [x, y]: all){
                f.pb(x); f.pb(y);
            }
            sort(f.begin(), f.end());
            int x = f[(int) (f.size() - 1) / 2];
            ll sum = 0;
            for (int i: f){
                sum += abs(i - x);
            }
            mn = sum + n;
        }
    }
    else {
        ll S = 0;
        for (auto [x, y]: all){
            S += (y - x);
        }
        
        int h = (int) imp.size();
        
        auto solve = [&](vector<int> f){
            if (f.empty()) return 0LL;
            ll out = inf;
            for (int i: f){
                ll sum = 0;
                for (int j: f){
                    sum += abs(i - j);
                }
                out = min(out, sum);
            }
            return out;
        };
        
        for (int j = 0; j < h; j++){
            int i = imp[j];
            ll sum = 0;
            for (auto [x, y]: all){
                if (x <= i && i <= y){
                    sum += (y - x);
                }
            }
            vector<int> f1;
            for (auto [x, y]: all){
                if (y < i){
                    f1.pb(x);
                    f1.pb(y);
                }
            }
            ll s1 = solve(f1);
            for (auto [x, y]: all){
                if (x > i){
                    s1 += ((x - i) + (y - i));
                }
            }
            
            vector<int> f2;
            for (auto [x, y]: all){
                if (x > i){
                    f2.pb(x);
                    f2.pb(y);
                }
            }
            ll s2 = solve(f2);
            for (auto [x, y]: all){
                if (y < i){
                    s2 += ((i - x) + (i - y));
                }
            }
            
            mn = min(mn, sum + s1 + n);
            mn = min(mn, sum + s2 + n);
        }
    }
    if (mn == inf) mn = 0;
    cout<<out + mn<<"\n";
}

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