Submission #635180

#	Time	Username	Problem	Language	Result	Execution time	Memory
635180		finn__	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	102 ms	3632 KiB

bridge

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

int main()
{
    size_t n, k;
    cin >> k >> n;

    vector<long> home, work;
    vector<long> positions;
    long cost = 0;

    for (size_t i = 0; i < n; i++)
    {
        char p, q;
        long s, t;
        cin >> p >> s >> q >> t;
        if (p != q)
        {
            home.push_back(s);
            work.push_back(t);
            positions.push_back(s);
            positions.push_back(t);
        }
        else
        {
            cost += abs(s - t);
        }
    }

    if (positions.empty())
    {
        cout << cost << '\n';
        return 0;
    }

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

    if (k == 1)
    {
        long median = positions[positions.size() / 2];
        for (size_t i = 0; i < home.size(); i++)
        {
            cost += abs(home[i] - median) + abs(work[i] - median) + 1;
        }
    }
    else
    {
        long third = positions[positions.size() / 3];
        long two_thirds = positions[positions.size() * 2 / 3];
        for (size_t i = 0; i < home.size(); i++)
        {
            cost += min(abs(home[i] - third) + abs(work[i] - third),
                        abs(home[i] - two_thirds) + abs(work[i] - two_thirds)) +
                    1;
        }
    }

    cout << cost << '\n';
}

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