Submission #1028695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028695		vjudge1	Palembang Bridges (APIO15_bridge)	C++17	31 / 100	2055 ms	3608 KiB

bridge

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

#define int long long
int const N=2e5+5;
int const inf=1e16;

vector<int> arr;
int pre[N];

void solve(){
    int n;
    cin>>n;
    vector<pair<int,int>> pr;
    set<int> st;
    int ex=0;
    for (int i = 0; i < n; ++i)
    {
        char c,d;
        int a,b;
        cin>>c>>a>>d>>b;
        if(c==d)
            ex+=abs(a-b);
        else{
            pr.push_back({a,b});
            st.insert(a);
            st.insert(b);
        }
    }
    n=pr.size();
    int ans=inf;
    for(int b1:st)
        for(int b2:st){
            int temp=n;
            for(auto [x,y]:pr)
                temp+=min(abs(x-b1)+abs(y-b1),abs(x-b2)+abs(y-b2));
            ans=min(ans,temp);
        }
    if(ans==inf)
        ans=0;
    cout<<ans+ex<<endl;
}

signed main(){
    int k,n;
    cin>>k;
    if(k==2){
        solve();
        return 0;
    }
    cin>>n;
    arr.push_back(0);
    char c,d;
    int a,b;
    int ex=n;
    for (int i = 1; i <=n; ++i){
        cin>>c>>a>>d>>b;
        if(c==d){
            ex--;
            ex+=abs(a-b);
        }
        else{
            arr.push_back(a);
            arr.push_back(b);
        }
    }
    sort(arr.begin(), arr.end());
    n=(arr.size())-1;
    for (int i = 1; i <=n; ++i)
        pre[i]=pre[i-1]+arr[i];
    int ans=pre[n];
    // cout<<ans<<endl;
    for(int i=1;i<=n;i++){
        ans=min(ans,((arr[i]*i)-pre[i])+((pre[n]-pre[i])-(arr[i]*(n-i))));
        // cout<<pre[i]<<endl;
    }
    cout<<ans+ex<<endl;
    return 0;
}

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