Submission #163885

#	Time	Username	Problem	Language	Result	Execution time	Memory
163885		combi1k1	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	325 ms	14688 KiB

bridge

#include<bits/stdc++.h>

using namespace std;

#define X   first
#define Y   second
#define ll  long long

typedef pair<int,int>   ii;

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int k;  cin >> k;
    int n;  cin >> n;

    ll  prev_sum = 0;

    vector<ii>  vec;

    for(int i = 1 ; i <= n ; ++i)   {
        char a, b;
        int  x, y;

        cin >> a >> x;
        cin >> b >> y;

        if (a == b) prev_sum += abs(x - y);
        if (a != b) {
            prev_sum++;
            if (x > y)  swap(x,y);
            vec.push_back(ii(x,y));
        }
    }

    sort(vec.begin(),vec.end(),[&](ii  x,ii  y) {
        return  x.X + x.Y < y.X + y.Y;
    });

    vector<ll>  f(vec.size() + 1,0);
    vector<ll>  g(vec.size() + 1,0);

    auto cal = [&](vector<ll> &v)   {
        multiset<int>   Min;
        multiset<int>   Max;

        ll  Sum_Max = 0;
        ll  Sum_Min = 0;
        ll  Med = 0;

        for(int i = 0 ; i < vec.size() ; ++i)   {
            if (vec[i].X <= Med && Med <= vec[i].Y) {
                Min.insert(vec[i].X);   Sum_Min += vec[i].X;
                Max.insert(vec[i].Y);   Sum_Max += vec[i].Y;
            }
            if (vec[i].X > Med) {
                Max.insert(vec[i].X);   Sum_Max += vec[i].X;
                Max.insert(vec[i].Y);   Sum_Max += vec[i].Y;
                int x = *(Max.begin());
                Max.erase(Max.begin()); Sum_Max -= x;
                Min.insert(x);          Sum_Min += x;
            }
            if (vec[i].Y < Med) {
                Min.insert(vec[i].X);   Sum_Min += vec[i].X;
                Min.insert(vec[i].Y);   Sum_Min += vec[i].Y;
                int x = *(--Min.end());
                Min.erase(--Min.end()); Sum_Min -= x;
                Max.insert(x);          Sum_Max += x;
            }

            v[i + 1] = Sum_Max - Sum_Min;

            Med = *(Max.begin());
        }
    };

    cal(f); reverse(vec.begin(),vec.end());
    cal(g); reverse(g.begin(),g.end());

    ll  ans = 1e18;

    for(int i = 0 ; i < (k == 1 ? 1 : f.size()) ; ++i)
        ans = min(ans,f[i] + g[i]);

    cout << ans + prev_sum << endl;
}
/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/

Compilation message (stderr)

bridge.cpp: In lambda function:
bridge.cpp:52:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0 ; i < vec.size() ; ++i)   {
                         ~~^~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:83:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < (k == 1 ? 1 : f.size()) ; ++i)
                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~

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