Submission #105304

#	Time	Username	Problem	Language	Result	Execution time	Memory
105304		win11905	Palembang Bridges (APIO15_bridge)	C++11	0 / 100	4 ms	516 KiB

bridge

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define x first
#define y second
#define long long long
using namespace std;

const int N = 1e5+5;

int k, n;
vector<pii> vec;
long ans;
long dp[2][N];

void solve_median(long dp[]) {
    priority_queue<int> Q1;
    priority_queue<int, vector<int>, greater<int> > Q2;
    long sum1 = 0, sum2 = 0;
    for(int i = 0; i < vec.size(); ++i) {
        Q1.emplace(vec[i].x), sum1 += vec[i].x;
        Q2.emplace(vec[i].y), sum2 += vec[i].y;
        while(Q1.top() > Q2.top()) {
            int u = Q1.top(), v = Q2.top();
            Q1.pop(), Q2.pop(); sum1 -= u, sum2 -= v;
            sum1 += v, sum2 += u;
            Q1.emplace(v), Q2.emplace(u);
        }
        dp[i] = ((i+1ll) * (Q1.top()) - sum1) + (sum2 - (i+1ll) * Q1.top());
    }
}

int main() {
    scanf("%d %d", &k, &n);
    for(int i = 0; i < n; ++i) {
        char a, b; int c, d;
        scanf(" %c %d %c %d", &a, &c, &b, &d);
        if(a == b) ans += abs(c - d);
        else vec.emplace_back(c, d);
    }
    ans += vec.size();
    sort(all(vec), [&](const pii &a, const pii &b) {
        return a.x + b.x < a.y + b.y;
    });
    solve_median(dp[0]); reverse(all(vec)); solve_median(dp[1]);
    if(k == 1) return !printf("%lld\n", ans + dp[0][vec.size()-1]);
    long val = dp[0][vec.size()-1];
    for(int i = 0; i < vec.size()-1; ++i) val = min(val, dp[0][i] + dp[1][vec.size()-i-2]);
    return !printf("%lld\n", ans + val);
}

Compilation message (stderr)

bridge.cpp: In function 'void solve_median(long long int*)':
bridge.cpp:20:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < vec.size(); ++i) {
                    ~~^~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:48:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < vec.size()-1; ++i) val = min(val, dp[0][i] + dp[1][vec.size()-i-2]);
                    ~~^~~~~~~~~~~~~~
bridge.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &k, &n);
     ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c %d %c %d", &a, &c, &b, &d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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