답안 #993355

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
993355	2024-06-05T14:02:50 Z	BF001	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	69 ms	7912 KB

bridge

#include <bits/stdc++.h>
using namespace std;

#define N 100005
#define int long long
#define fi first
#define se second

typedef pair<int, int> ii;

int same, res, n, lsum, rsum, pre[N];
vector<ii> vec;
priority_queue<int> lq;
priority_queue<int, vector<int>, greater<int>> rq;

void add(int x){
	//cout << x << "\n";
	int tp = 1e18;
	if (lq.size()) tp = lq.top();
	if (x <= tp){
		lq.push(x);
		lsum += x;
	}
	else {
		rq.push(x);
		rsum += x;
	}
	if (rq.size() + 1 < lq.size()){
		tp = lq.top();
		lq.pop();
		rq.push(tp);
		rsum += tp;
		lsum -= tp;
	}
	if (lq.size() < rq.size()){
		tp = rq.top();
		rq.pop();
		lq.push(tp);
		rsum -= tp;
		lsum += tp;
	}
}

bool cmp(ii& a, ii& b){
	return a.fi + a.se < b.fi + b.se;
}

int k;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
     
    cin >> k >> n;
    for (int i = 1; i <= n; i++){
    	char aa, bb;
    	int pos1, pos2;
    	cin >> aa >> pos1 >> bb >> pos2;
    	if (aa == bb){
    		same += abs(pos2 - pos1);
    	}
    	else{
    		vec.push_back({pos1, pos2});
    	}
    }  

    sort(vec.begin(), vec.end(), cmp);

    same += vec.size();

    for (int i = 1; i <= (int) vec.size(); i++){
    	add(vec[i - 1].fi);
    	add(vec[i - 1].se);
    	//cout << rsum << " " << lsum << "\n";
    	pre[i] = rsum - lsum;
    }

    res = pre[vec.size()];
    if (k == 2){
	    lsum = rsum = 0;
	    while (lq.size()) lq.pop();
	    while (rq.size()) rq.pop();
	    for (int i = (int) vec.size(); i >= 1; i--){
	    	add(vec[i - 1].fi);
	    	add(vec[i - 1].se);
	    	res = min(res, pre[i - 1] + rsum - lsum);
	    }
	}
    cout << res + same;

    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	472 KB	Output is correct
8	Correct	1 ms	600 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	20 ms	6888 KB	Output is correct
13	Correct	43 ms	7628 KB	Output is correct
14	Correct	34 ms	6344 KB	Output is correct
15	Correct	24 ms	5072 KB	Output is correct
16	Correct	24 ms	7060 KB	Output is correct
17	Correct	30 ms	7884 KB	Output is correct
18	Correct	29 ms	7116 KB	Output is correct
19	Correct	35 ms	7884 KB	Output is correct
20	Correct	27 ms	7376 KB	Output is correct
21	Correct	34 ms	7640 KB	Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

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

Subtask #5
37.0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	352 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	352 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	352 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	504 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	352 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	0 ms	352 KB	Output is correct
19	Correct	1 ms	356 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	1 ms	352 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	344 KB	Output is correct
24	Correct	1 ms	492 KB	Output is correct
25	Correct	29 ms	6512 KB	Output is correct
26	Correct	56 ms	6596 KB	Output is correct
27	Correct	65 ms	7460 KB	Output is correct
28	Correct	69 ms	7912 KB	Output is correct
29	Correct	67 ms	7592 KB	Output is correct
30	Correct	35 ms	4044 KB	Output is correct
31	Correct	31 ms	6872 KB	Output is correct
32	Correct	50 ms	7888 KB	Output is correct
33	Correct	49 ms	7888 KB	Output is correct
34	Correct	59 ms	7624 KB	Output is correct
35	Correct	34 ms	7384 KB	Output is correct
36	Correct	55 ms	7696 KB	Output is correct
37	Correct	24 ms	6356 KB	Output is correct

답안 #993355

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