답안 #361435

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
361435	2021-01-30T07:47:16 Z	alireza_kaviani	Palembang Bridges (APIO15_bridge)	C++11	100 / 100	96 ms	9200 KB

bridge

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

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)						(x).begin(),(x).end()
#define X							first
#define Y							second
#define sep							' '
#define endl						'\n'
#define SZ(x)						ll(x.size())

const ll MAXN = 1e6 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

ll k , n , ans , pref[MAXN] , suff[MAXN] , ps[MAXN] , sum;
priority_queue<ll> pq;
priority_queue<ll , vector<ll> , greater<ll>> pq2;
vector<pll> vec;

void insert(ll x){
	if(SZ(pq) && x < pq.top()) pq.push(x) , sum -= x;
	else	pq2.push(x) , sum += x;
	while(SZ(pq) > SZ(pq2)){
		x = pq.top(); pq.pop(); pq2.push(x);
		sum += 2 * x;
	}
	while(SZ(pq2) > SZ(pq) + 1){
		x = pq2.top(); pq2.pop(); pq.push(x);
		sum -= 2 * x;
	}
	assert(SZ(pq2) >= SZ(pq));
	assert(SZ(pq) == 0 || pq2.top() >= pq.top());
//	exit(0);
}

ll solve(){
	ll x = pq2.top();
	return sum + x * (SZ(pq) - SZ(pq2));
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin >> k >> n;
	for(int i = 0 ; i < n ; i++){
		string A , B;
		int x , y;
		cin >> A >> x >> B >> y;
		if(A == B){
			ans += abs(x - y);
			continue;
		}
		ans++;
		vec.push_back({x + y , y});
	}
	if(SZ(vec) == 0)	return cout << ans << endl , 0;
	sort(all(vec));
	n = SZ(vec);
//	pq.push(1)a; pq.push(1);
//	cout << SZ(pq) << endl;
	for(int i = 0 ; i < n ; i++){
		insert(vec[i].X - vec[i].Y);
		insert(vec[i].Y);
		pref[i] = solve();
	}
	pq = {};  pq2 = {}; sum = 0;
	for(int i = n - 1 ; i >= 0 ; i--){
		insert(vec[i].X - vec[i].Y);
		insert(vec[i].Y);
		suff[i] = solve();
	}
	ll res = pref[n - 1] + ans;
	for(int i = 0 ; i + 1 < n && k == 2 ; i++){
		res = min(res , pref[i] + suff[i + 1] + ans);
	}
	cout << res << endl;

    return 0;
}
/*

*/

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	512 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	2 ms	364 KB	Output is correct
12	Correct	54 ms	6548 KB	Output is correct
13	Correct	92 ms	6504 KB	Output is correct
14	Correct	77 ms	6016 KB	Output is correct
15	Correct	54 ms	4084 KB	Output is correct
16	Correct	64 ms	6384 KB	Output is correct
17	Correct	76 ms	6384 KB	Output is correct
18	Correct	81 ms	6492 KB	Output is correct
19	Correct	79 ms	6464 KB	Output is correct
20	Correct	62 ms	6492 KB	Output is correct
21	Correct	87 ms	6540 KB	Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

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

Subtask #5
37.0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	492 KB	Output is correct
15	Correct	1 ms	396 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	1 ms	384 KB	Output is correct
19	Correct	1 ms	492 KB	Output is correct
20	Correct	1 ms	492 KB	Output is correct
21	Correct	1 ms	492 KB	Output is correct
22	Correct	1 ms	492 KB	Output is correct
23	Correct	1 ms	492 KB	Output is correct
24	Correct	2 ms	492 KB	Output is correct
25	Correct	54 ms	7280 KB	Output is correct
26	Correct	74 ms	8048 KB	Output is correct
27	Correct	90 ms	8656 KB	Output is correct
28	Correct	96 ms	9024 KB	Output is correct
29	Correct	94 ms	9200 KB	Output is correct
30	Correct	49 ms	4724 KB	Output is correct
31	Correct	65 ms	8176 KB	Output is correct
32	Correct	73 ms	9120 KB	Output is correct
33	Correct	80 ms	8432 KB	Output is correct
34	Correct	79 ms	8844 KB	Output is correct
35	Correct	61 ms	8472 KB	Output is correct
36	Correct	76 ms	8560 KB	Output is correct
37	Correct	51 ms	7280 KB	Output is correct

답안 #361435

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