Submission #469835

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
469835	2021-09-02T04:48:07 Z	training4usaco	Palembang Bridges (APIO15_bridge)	C++11	100 / 100	411 ms	14364 KB

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.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	3 ms	204 KB	Output is correct
3	Correct	2 ms	332 KB	Output is correct
4	Correct	2 ms	332 KB	Output is correct
5	Correct	2 ms	332 KB	Output is correct
6	Correct	2 ms	332 KB	Output is correct
7	Correct	2 ms	332 KB	Output is correct
8	Correct	2 ms	432 KB	Output is correct
9	Correct	3 ms	428 KB	Output is correct
10	Correct	2 ms	332 KB	Output is correct
11	Correct	2 ms	332 KB	Output is correct

Subtask #2
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	2 ms	332 KB	Output is correct
5	Correct	2 ms	332 KB	Output is correct
6	Correct	2 ms	432 KB	Output is correct
7	Correct	2 ms	332 KB	Output is correct
8	Correct	2 ms	332 KB	Output is correct
9	Correct	2 ms	332 KB	Output is correct
10	Correct	2 ms	332 KB	Output is correct
11	Correct	2 ms	332 KB	Output is correct
12	Correct	134 ms	12724 KB	Output is correct
13	Correct	244 ms	14300 KB	Output is correct
14	Correct	174 ms	12020 KB	Output is correct
15	Correct	124 ms	8608 KB	Output is correct
16	Correct	192 ms	13636 KB	Output is correct
17	Correct	184 ms	14352 KB	Output is correct
18	Correct	146 ms	13876 KB	Output is correct
19	Correct	198 ms	14352 KB	Output is correct
20	Correct	174 ms	13808 KB	Output is correct
21	Correct	183 ms	14024 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct

Subtask #4
32.0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	236 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	2 ms	332 KB	Output is correct
14	Correct	2 ms	332 KB	Output is correct
15	Correct	3 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	2 ms	332 KB	Output is correct
20	Correct	3 ms	332 KB	Output is correct
21	Correct	2 ms	332 KB	Output is correct
22	Correct	2 ms	332 KB	Output is correct
23	Correct	2 ms	332 KB	Output is correct
24	Correct	2 ms	432 KB	Output is correct

Subtask #5
37.0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	2 ms	404 KB	Output is correct
14	Correct	2 ms	332 KB	Output is correct
15	Correct	3 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	2 ms	332 KB	Output is correct
20	Correct	2 ms	332 KB	Output is correct
21	Correct	3 ms	332 KB	Output is correct
22	Correct	2 ms	332 KB	Output is correct
23	Correct	2 ms	332 KB	Output is correct
24	Correct	2 ms	332 KB	Output is correct
25	Correct	213 ms	12744 KB	Output is correct
26	Correct	323 ms	12944 KB	Output is correct
27	Correct	397 ms	13804 KB	Output is correct
28	Correct	411 ms	14212 KB	Output is correct
29	Correct	397 ms	14364 KB	Output is correct
30	Correct	169 ms	7616 KB	Output is correct
31	Correct	218 ms	13652 KB	Output is correct
32	Correct	259 ms	14284 KB	Output is correct
33	Correct	212 ms	13876 KB	Output is correct
34	Correct	255 ms	14312 KB	Output is correct
35	Correct	235 ms	13780 KB	Output is correct
36	Correct	253 ms	13964 KB	Output is correct
37	Correct	206 ms	12820 KB	Output is correct

Submission #469835

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 14.0 / 14.0

Subtask #3 9.0 / 9.0

Subtask #4 32.0 / 32.0

Subtask #5 37.0 / 37.0

Subtask #1
8.0 / 8.0

Subtask #2
14.0 / 14.0

Subtask #3
9.0 / 9.0

Subtask #4
32.0 / 32.0

Subtask #5
37.0 / 37.0