Submission #469834

#	Time	Username	Problem	Language	Result	Execution time	Memory
469834		training4usaco	Palembang Bridges (APIO15_bridge)	C++11	0 / 100	2 ms	332 KiB

bridge

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

#define INF 1000000009

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

void build(int val) {
    int 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()) {
		int moved = *lower.rbegin();
		lower.erase(lower.find(moved));
		upper.insert(moved);
		lsum -= moved;
		usum += moved;
	} 
    else if (lower.size() < upper.size()) {
		int moved = *upper.begin();
		upper.erase(upper.find(moved));
		lower.insert(moved);
		usum -= moved;
		lsum += moved;
	}
}

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

vector<int> pref_sum;

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

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

    vector<pair<int, int>> locs;
    locs.push_back({0, 0});
    int same = 0;
    for(int i = 0; i < n; ++i) {
        char a, b;
        int 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);

	int new_n = locs.size() - 1;

	same += new_n;

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

	int ans = pref_sum[new_n];

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

		lsum = 0;
        usum = 0;

		for (int 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: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37