Submission #966255

#	Time	Username	Problem	Language	Result	Execution time	Memory
966255		Neco_arc	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	164 ms	16360 KiB

bridge

#include <bits/stdc++.h>

#define ll long long
#define all(x) x.begin(), x.end()
#define Neco "Palembang Bridges"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 2e5 + 7

using namespace std;

const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll GetRandom(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r)(rng);
}

int n, N, k;
ll Sum, pre[maxn], suf[maxn];
ll Sum1, Sum2, ans = 1e18;
multiset<int> S1, S2;
pair<int, int> a[maxn];

void Peko() {
    if(S2.size() > S1.size()) {
        int val = *S2.begin();
        S1.insert(val), S2.erase(S2.begin());
        Sum1 -= val, Sum2 -= val;
    }

    if(S1.size() > S2.size() + 1) {
        int val = *S1.rbegin();
        S1.erase(prev(S1.end())), S2.insert(val);
        Sum1 += val, Sum2 += val;
    }
}

void Add(int x) {
    int mid = S1.empty() ? 0 : *S1.rbegin();
    if(x > mid) S2.insert(x), Sum2 += x;
    else S1.insert(x), Sum1 -= x;

    Peko();
}

void solve()
{

    cin >> k >> n;
    fi(i, 1, n) {
        char T1, T2; int x, y;
        cin >> T1 >> x >> T2 >> y;

        if(T1 == T2) Sum += abs(x - y);
        else a[++N] = {x, y};
    }

    sort(a + 1, a + 1 + N, [](pair<int, int> x, pair<int, int> y) { return x.first + x.second < y.first + y.second; } );

    fi(i, 1, N) {
        Add(a[i].first), Add(a[i].second);
        ll mid = *S1.rbegin(), L1 = S1.size(), L2 = S2.size();

        pre[i] = mid * L1 - mid * L2 + Sum1 + Sum2;
    }

    S1.clear(), S2.clear(), Sum1 = Sum2 = 0;

    fid(i, N, 1) {
        Add(a[i].first), Add(a[i].second);
        ll mid = *S1.rbegin(), L1 = S1.size(), L2 = S2.size();
        suf[i] = mid * L1 - mid * L2 + Sum1 + Sum2;
    }

    if(k == 1) ans = Sum + suf[1];
    else
    {
        fi(i, 0, N) ans = min(ans, Sum + pre[i] + suf[i + 1]);
    }

    cout << ans + N;

}


int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(Neco".inp", "r")) {
        freopen(Neco".inp", "r", stdin);
        freopen(Neco".out", "w", stdout);
    }


    int nTest = 1;
//    cin >> nTest;


    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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