Submission #107010

#	Time	Username	Problem	Language	Result	Execution time	Memory
107010		someone_aa	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	177 ms	3972 KiB

bridge

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
ll s[maxn], f[maxn], n, k;
char szone[maxn], fzone[maxn];

int main() {
    cin>>k>>n;
    ll result = 0LL;

    vector<ll>v;
    vector<pair<ll,ll> > vv;
    for(int i=1;i<=n;i++) {
        cin>>szone[i]>>s[i];
        cin>>fzone[i]>>f[i];
        if(szone[i] == fzone[i]) result += abs(f[i] - s[i]);
        if(szone[i] != fzone[i]) {
            v.pb(s[i]);
            v.pb(f[i]);
        }

        if(s[i] > f[i]) swap(s[i], f[i]);
    }

    if(v.size() == 0) {
        cout<<result;
        return 0;
    }

    if(k == 1) {
        ll mintemp = LLONG_MAX;
        sort(v.begin(), v.end());

        // 0 1 2 3

        int half = v[0];
        if(v.size() > 1)
            half = v[v.size()/2-1];
        else half = v.back();
        for(int d=half-1;d<=half+1;d++) {
            ll temp = 0LL;
            for(int i=1;i<=n;i++) {
                if(szone[i] != fzone[i]) {
                    temp += abs(f[i] - d) + abs(s[i] - d) + 1;
                }
            }
            //cout<<d<<": "<<temp<<"\n";
            mintemp = min(mintemp, temp);
        }

        result += mintemp;
        cout<<result<<"\n";
        return 0;
    }
    else if(k == 2) {
        sort(v.begin(), v.end());
        ll mintemp = LLONG_MAX;
        for(int i:v) {
            vector<int>v2;
            ll temp = 0LL;
            for(int j=1;j<=n;j++) {
                if(fzone[j] == szone[j]) continue;

                if(!(s[j] <= i && i <= f[j])) {
                    v2.pb(s[j]);
                    v2.pb(f[j]);
                }
                else {
                    temp += abs(s[j] - i) + abs(f[j] - i);
                }
            }

            /*cout<<i<<": \n";
            for(int i:v2) {
                cout<<i<<" ";
            } cout<<" - "<<temp<<" -> ";*/

            sort(v2.begin(), v2.end());

            if(v2.size() == 0) continue;
            int half = v2[0];
            if(v2.size() > 1)
                half = v2[v2.size()/2-1] ;
            else half = v2.back();

            for(int j:v2) {
                temp += abs(j - half);
            }

            temp += v.size() / 2;

            //cout<<temp<<"\n";

            mintemp = min(mintemp, temp);
        }
        cout<<result+mintemp;
    }

    return 0;
}

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