Submission #110205

#	Time	Username	Problem	Language	Result	Execution time	Memory
110205		SamAnd	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	140 ms	6636 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;

int k, n;

long long ans;

vector<int> a;
long long p[N * 2], s[N * 2];

int main()
{
    cin >> k >> n;
    for (int i = 1; i <= n; ++i)
    {
        char xx;
        int x;
        char yy;
        int y;
        cin >> xx >> x >> yy >> y;
        if (xx == yy)
            ans += abs(x - y);
        else
        {
            a.push_back(x);
            a.push_back(y);
        }
    }
    sort(a.begin(), a.end());
    ans += (a.size() / 2);

    for (int i = 1; i < a.size(); ++i)
        p[i] = p[i - 1] + (a[i] - a[i - 1]) * 1LL * i;

    for (int i = a.size() - 2; i >= 0; --i)
        s[i] = s[i + 1] + (a[i + 1] - a[i]) * 1LL * (a.size() - i - 1);

    long long pans = p[0] + s[0];
    for (int i = 1; i < a.size(); ++i)
        pans = min(pans, p[i] + s[i]);

    cout << ans + pans << endl;
    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:33:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < a.size(); ++i)
                     ~~^~~~~~~~~~
bridge.cpp:40:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < a.size(); ++i)
                     ~~^~~~~~~~~~

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