Submission #380464

#	Time	Username	Problem	Language	Result	Execution time	Memory
380464		LittleCube	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	50 ms	3308 KiB

bridge

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#pragma pack(0)
#define ll long long
#define pii pair<ll, ll>
#define pll pair<ll, ll>
#define F first
#define S second
#define MOD 1000000007
#define MOD2 998244353
#define _INFINITY 9223372036854775807
#define fast ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

ll n, k, ans1, ans2 = 1e15;
vector<int> v;
vector<pii> u;
signed main()
{
    fast;
    cin >> k >> n;
    for (int i = 1; i <= n; i++)
    {
        char c1, c2;
        int p1, p2;
        cin >> c1 >> p1 >> c2 >> p2;
        if (c1 == c2)
            ans1 += 2 * abs(p1 - p2);
        else
        {
            v.emplace_back(p1);
            v.emplace_back(p2);
            u.emplace_back(make_pair(p1, p2));
        }
    }
    sort(v.begin(), v.end());
    if (k == 1)
    {
        ans2 = 0;
        if (v.size() % 2)
        {
            int mid = 2 * v[v.size() / 2];
            for (int i : v)
                ans2 += abs(mid - i * 2) + 1;
        }
        else if (v.size() > 0)
        {
            int mid = v[v.size() / 2] + v[v.size() / 2 - 1];
            for (int i : v)
                ans2 += abs(mid - i * 2) + 1;
        }
        cout << (ans2 + ans1) / 2 << '\n';
    }
    else
    {
        for (int i : v)
            for (int j : v)
            {
                ll res = 0;
                for (pii p : u)
                    res += min(abs(p.F - i) + abs(p.S - i) + 1, abs(p.F - j) + abs(p.S - j) + 1);
                ans2 = min(ans2, res);
            }
        cout << ans1 / 2 + ans2 << '\n';
    }
}

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