답안 #111095

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
111095	2019-05-13T15:49:55 Z	square1001	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	96 ms	6456 KB

bridge

#include <cmath>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const long long inf = 1LL << 62;
long long solve(int K, int N, vector<int> A, vector<int> B) {
	if(N == 0) return 0;
	vector<int> perm(N);
	for(int i = 0; i < N; ++i) perm[i] = i;
	sort(perm.begin(), perm.end(), [&](int i, int j) { return A[i] + B[i] < A[j] + B[j]; });
	vector<int> SA(N), SB(N);
	for(int i = 0; i < N; ++i) SA[i] = A[perm[i]], SB[i] = B[perm[i]];
	A = SA, B = SB;
	vector<long long> da(N + 1), db(N + 1);
	long long sum = 0, all = 0, last = -1;
	priority_queue<int> que;
	for(int i = 1; i <= N; ++i) {
		que.push(-A[i - 1]);
		que.push(-B[i - 1]);
		last = -que.top();
		que.pop();
		sum += last;
		all += A[i - 1] + B[i - 1];
		da[i] = (last * i - sum) + ((all - sum) - last * i);
	}
	sum = 0, all = 0, last = -1;
	que = priority_queue<int>();
	for(int i = 1; i <= N; ++i) {
		que.push(A[N - i]);
		que.push(B[N - i]);
		last = que.top();
		que.pop();
		sum += last;
		all += A[N - i] + B[N - i];
		db[N - i] = (sum - last * i) + (last * i - (all - sum));
	}
	long long ans = inf;
	for(int i = 0; i < (K == 1 ? 1 : N); ++i) {
		ans = min(ans, da[i] + db[i]);
	}
	return ans + N;
}
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int K, N;
	cin >> K >> N;
	vector<int> A, B;
	long long offset = 0;
	for(int i = 0; i < N; ++i) {
		string P, Q; int S, T;
		cin >> P >> S >> Q >> T;
		if(P != Q) {
			A.push_back(S);
			B.push_back(T);
		}
		else offset += abs(S - T);
	}
	N = A.size();
	long long ans = solve(K, N, A, B);
	cout << ans + offset << endl;
	return 0;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct
7	Correct	3 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	3 ms	384 KB	Output is correct
10	Correct	3 ms	384 KB	Output is correct
11	Correct	3 ms	384 KB	Output is correct

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	3 ms	384 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	3 ms	384 KB	Output is correct
9	Correct	3 ms	384 KB	Output is correct
10	Correct	3 ms	384 KB	Output is correct
11	Correct	3 ms	384 KB	Output is correct
12	Correct	75 ms	5732 KB	Output is correct
13	Correct	88 ms	5728 KB	Output is correct
14	Correct	73 ms	5260 KB	Output is correct
15	Correct	46 ms	3460 KB	Output is correct
16	Correct	62 ms	5732 KB	Output is correct
17	Correct	67 ms	5732 KB	Output is correct
18	Correct	96 ms	5760 KB	Output is correct
19	Correct	75 ms	5700 KB	Output is correct
20	Correct	51 ms	5732 KB	Output is correct
21	Correct	62 ms	5732 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	3 ms	384 KB	Output is correct

Subtask #4
32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	6 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	3 ms	384 KB	Output is correct
11	Correct	3 ms	384 KB	Output is correct
12	Correct	3 ms	384 KB	Output is correct
13	Correct	3 ms	384 KB	Output is correct
14	Correct	4 ms	384 KB	Output is correct
15	Correct	3 ms	384 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	3 ms	384 KB	Output is correct
18	Correct	3 ms	384 KB	Output is correct
19	Correct	3 ms	384 KB	Output is correct
20	Correct	4 ms	384 KB	Output is correct
21	Correct	3 ms	384 KB	Output is correct
22	Correct	3 ms	384 KB	Output is correct
23	Correct	3 ms	384 KB	Output is correct
24	Correct	4 ms	384 KB	Output is correct

Subtask #5
37.0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	3 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	3 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	3 ms	384 KB	Output is correct
16	Correct	4 ms	384 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	3 ms	384 KB	Output is correct
19	Correct	3 ms	384 KB	Output is correct
20	Correct	4 ms	384 KB	Output is correct
21	Correct	4 ms	512 KB	Output is correct
22	Correct	3 ms	384 KB	Output is correct
23	Correct	3 ms	384 KB	Output is correct
24	Correct	3 ms	384 KB	Output is correct
25	Correct	70 ms	6348 KB	Output is correct
26	Correct	72 ms	6372 KB	Output is correct
27	Correct	94 ms	6300 KB	Output is correct
28	Correct	90 ms	6364 KB	Output is correct
29	Correct	91 ms	6372 KB	Output is correct
30	Correct	58 ms	3876 KB	Output is correct
31	Correct	61 ms	6372 KB	Output is correct
32	Correct	63 ms	6372 KB	Output is correct
33	Correct	62 ms	6456 KB	Output is correct
34	Correct	80 ms	6296 KB	Output is correct
35	Correct	95 ms	6244 KB	Output is correct
36	Correct	78 ms	6320 KB	Output is correct
37	Correct	46 ms	6344 KB	Output is correct

답안 #111095

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