Submission #881595

#	Time	Username	Problem	Language	Result	Execution time	Memory
881595		AnhPham	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	31 ms	4364 KiB

bridge

#include <bits/stdc++.h>

#ifdef OP_DEBUG
    #include <algo/debug.h>
#else
    #define debug(...) 26
#endif

using namespace std;

#define int 	long long // maybe tle?
#define sz(v)   (int)(v).size()
#define all(v)  (v).begin(), (v).end()
#define TcT     template <class T

const   int     MOD = (int)1e9 + 7, INF = (int)2e9 + 9, INF64 = (int)4e18 + 18;

TcT>            bool minimize(T &val, const T &upd) { return upd < val ? val = upd, 1 : 0; }
TcT>            bool maximize(T &val, const T &upd) { return upd > val ? val = upd, 1 : 0; }

TcT, class S>   istream &operator >> (istream &scanf, pair <T, S> &u) { return scanf >> u.first >> u.second;        }
TcT, class S>   ostream &operator << (ostream &print, pair <T, S> &u) { return print << u.first << ' ' << u.second; }

void solve();

int32_t main() {
    cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(0);
    int testcases = 1;

#define TC 0
    if (TC) { cin >> testcases; } for (; testcases--;) { solve(); }
}

/* [Pham Hung Anh - 11I - Tran Hung Dao High School for Gifted Student] */

int k, n;

namespace sub12 {
    void solve() {
        int ans = 0;
        vector <int> buildings;

        for (int i = 1; i <= n; ++i) {
            char p, q; int s, t; cin >> p >> s >> q >> t;

            if (p == q)
                ans += abs(s - t);
            else
                buildings.push_back(s), buildings.push_back(t);
        }

        if (sz(buildings) == 0)
            return void(cout << ans << '\n');

        sort(all(buildings));

        int m = sz(buildings);
        int median = buildings[(m + 1) / 2];

        for (int i = 0; i < m; ++i)
            ans += abs(median - buildings[i]);
        
        cout << ans + sz(buildings) / 2 << '\n';
    }
}

namespace sub3 {
    void solve() {
        int ans = 0;
        vector <int> buildings;
        vector <pair <int, int>> opposite;

        for (int i = 1; i <= n; ++i) {
            char p, q; int s, t; cin >> p >> s >> q >> t;

            if (p == q)
                ans += abs(s - t);
            else
                buildings.push_back(s), buildings.push_back(t), opposite.emplace_back(min(s, t), max(s, t));
        }

        if (sz(buildings) == 0)
            return void(cout << ans << '\n');

        int res = INF;
        for (int i = 0; i < sz(buildings); ++i)
            for (int j = i + 1; j < sz(buildings); ++j) {
                int r1 = buildings[i], r2 = buildings[j];
                int sum = 0;
                for (auto p : opposite)
                    sum += min(abs(p.first - r1) + abs(p.second - r1), abs(p.first - r2) + abs(p.second - r2)) + 1;
                
                minimize(res, sum);
            }
            
        cout << ans + res << '\n';
    }
}

namespace sub4 {
    void solve() {

    }
}

namespace sub5 {
    void solve() {
        
    }
}

void solve() {
    cin >> k >> n;

    if (k == 1)
        sub12 :: solve();
    else {
        if (n <= 100)
            sub3 :: solve();
        else if (n <= 1000)
            sub4 :: solve();
        else
            sub5 :: solve();
    }
}

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