Submission #1054231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054231		unnick	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	62 ms	1608 KiB

bridge

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long int ll;

int main() {
    int k, n;
    cin >> k >> n;
    if (k != 1) {
        vector<int> as;
        vector<int> ae;
        vector<int> a;
        ll sum = 0;

        for (int i = 0; i < n; i++) {
            char sa, sb;
            int ia, ib;
            cin >> sa >> ia >> sb >> ib;
            if (sa == sb) {
                sum += abs(ia-ib);
                continue;
            }
            as.push_back(ia);
            ae.push_back(ib);
            a.push_back(ia);
            a.push_back(ib);
            sum += 1;
        }
        ll bs = 0x7FFFFFFFFFFFFFFFll;
        for (auto p1 : a) {
            for (auto p2 : a) {
                ll s = 0;
                for (int i = 0; i < as.size(); i++) {
                    s += min(abs(as[i]-p1) + abs(ae[i]-p1), abs(as[i]-p2) + abs(ae[i]-p2));
                }
                bs = min(bs, s);
            }
        }

        sum += bs;

        cout << sum << "\n";

        return 0;
    }

    vector<int> a;
    ll sum = 0;

    for (int i = 0; i < n; i++) {
        char sa, sb;
        int ia, ib;
        cin >> sa >> ia >> sb >> ib;
        if (sa == sb) {
            sum += abs(ia-ib);
            continue;
        }
        a.push_back(ia);
        a.push_back(ib);
        sum += 1;
    }

    sort(a.begin(), a.end());
    int p = a[a.size() / 2];

    for (auto v : a) {
        sum += abs(v-p);
    }

    cout << sum << "\n";
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:36:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |                 for (int i = 0; i < as.size(); i++) {
      |                                 ~~^~~~~~~~~~~

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