Submission #1028685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028685		vjudge1	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	69 ms	5868 KiB

bridge

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

#define int long long
int const N=2e5+5;
int const mod=1e9+7;

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

signed main(){
    int k,n;
    cin>>k>>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: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37