Submission #469835

#	Time	Username	Problem	Language	Result	Execution time	Memory
469835		training4usaco	Palembang Bridges (APIO15_bridge)	C++11	100 / 100	411 ms	14364 KiB

bridge

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

#define INF 1000000009

multiset<long long> upper;
multiset<long long> lower;
long long lsum, usum;

void build(long long val) {
    long long median;
    if(lower.empty()) {
        median = INF;
    } 
    else{
        median = *lower.rbegin();
    } 
    if (val <= median) {
        lower.insert(val);
		lsum += val;
	} 
    else {
		upper.insert(val);
		usum += val;
	}

	if (upper.size() + 1 < lower.size()) {
		long long moved = *lower.rbegin();
		lower.erase(lower.find(moved));
		upper.insert(moved);
		lsum -= moved;
		usum += moved;
	} 
    else if (lower.size() < upper.size()) {
		long long moved = *upper.begin();
		upper.erase(upper.find(moved));
		lower.insert(moved);
		usum -= moved;
		lsum += moved;
	}
}

bool comp(pair<long long, long long> a, pair<long long, long long> b) {
    return a.first + a.second < b.first + b.second;
}

vector<long long> pref_sum;

int main() {
    long long n, k;
    cin >> k >> n;

    pref_sum = vector<long long>(n + 1);

    vector<pair<long long, long long>> locs;
    locs.push_back({0, 0});
    long long same = 0;
    for(long long i = 0; i < n; ++i) {
        char a, b;
        long long c, d;
        cin >> a >> c >> b >> d;

        if(a == b) {
            same += abs(c - d);
        }
        else {
            locs.push_back({c, d});
        }
    }

    sort(locs.begin(), locs.end(), comp);

	long long new_n = locs.size() - 1;

	same += new_n;

    for(long long i = 1; i <= new_n; ++i) {
        build(locs[i].first);
        build(locs[i].second);
        pref_sum[i] = usum - lsum;
    }

	long long ans = pref_sum[new_n];

	if (k == 2) {
		lower.clear();
        upper.clear();

		lsum = 0;
        usum = 0;

		for (long long i = new_n; i > 0; i--) {
			build(locs[i].first);
			build(locs[i].second);
			ans = min(ans, usum - lsum + pref_sum[i - 1]);
		}
	}

	cout << same + ans << endl;
    return 0;
}

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