Submission #462057

#	Time	Username	Problem	Language	Result	Execution time	Memory
462057		prvocislo	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	293 ms	14384 KiB

bridge

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
typedef long long ll;
using namespace std;

multiset<int, greater<int>> small; multiset<int> big;
ll sumsmall = 0, sumbig = 0;
void addsmall(int x) { small.insert(x), sumsmall += x; }
void popsmall() { sumsmall -= *small.begin(), small.erase(small.begin()); }
void addbig(int x) { big.insert(x), sumbig += x; }
void popbig() { sumbig -= *big.begin(), big.erase(big.begin()); }
void insert(int x)
{
    int m = (big.empty() ? -1 : *big.begin());
    if (x < m) addsmall(x);
    else addbig(x);
    if (small.size() > big.size()) addbig(*small.begin()), popsmall();
    if (small.size() + 1 < big.size()) addsmall(*big.begin()), popbig();
}
struct segment { int l, r; };
vector<ll> solve(const vector<segment>& s) // l a r budu 1 indexovane
{
    int n = s.size() - 1;
    small.clear(), big.clear(), sumsmall = 0, sumbig = 0;
    vector<ll>ans(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        insert(s[i].l), insert(s[i].r);
        ll x = *prev(big.end());
        ans[i] = x * (ll)small.size() - sumsmall + sumbig - x * (ll)big.size();
    }
    return ans;
}
bool cmp(const segment& a, const segment& b) { return a.l + a.r < b.l + b.r; }
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int k, n;
    cin >> k >> n;
    vector<segment> v(1, { 0, 0 });
    ll sum = 0;
    for (int i = 0; i < n; i++)
    {
        char c1, c2; int l1, l2;
        cin >> c1 >> l1 >> c2 >> l2;
        if (c1 != c2) v.push_back({ l1, l2 }), sum++;
        else sum += abs(l1 - l2);
    }
    n = v.size()-1;
    sort(v.begin()+1, v.end(), cmp);
    vector<ll> ans1 = solve(v);
    if (k == 1)
    {
        cout << ans1[n] + sum << "\n";
        return 0;
    }
    reverse(v.begin() + 1, v.end());
    for (int i = 1; i <= n; i++) v[i] = { -v[i].r, -v[i].l };
    vector<ll> ans2 = solve(v);
    ll ans = 1e18;
    for (int i = 0; i <= n; i++)
    {
        ans = min(ans, ans1[i] + ans2[n - i]);
    }
    cout << ans + sum << "\n";
    return 0;
}

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