oj.uz

답안 #1083190

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1083190 2024-09-02T17:40:01 Z damamila Palembang Bridges (APIO15_bridge) C++17
22 / 100
 33 ms 6752 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);  
	int k, n;
	cin >> k >> n;
	int m = n;
	vector<tuple<int, int, int>> num;
	vector<int> all;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int a, b;
		char c, d;
		cin >> c >> a >> d >> b;
		if (c == d) {
			m--;
			ans += abs(b-a);
		} else {
			ans++;
			all.push_back(a);
			all.push_back(b);
			num.push_back({a+b, a, b});
		}
	}
	sort(all.begin(), all.end());
	if (k == 1) {
		int x = all[all.size()/2];
		for (int i : all) {
			ans += abs(i-x);
		}
		cout << ans << endl;
	} else {
		sort(num.begin(), num.end());
		multiset<int> rbig;
		multiset<int> rsmall;
		multiset<int> lbig;
		multiset<int> lsmall;
		int rbigsum = 0, lbigsum = 0, rsmallsum = 0, lsmallsum = 0;
		for (int i = 0; i < all.size(); i++) {
			if (i <= all.size()/2) {
				rsmall.insert(all[i]);
				rsmallsum += all[i];
			} else {
				rbig.insert(all[i]);
				rbigsum += all[i];
			}
		}
		auto it = rsmall.end(); it--;
		int rmed = *it, lmed = 0;
		int res = 1e9; //biggest
		//~ cout << "YAYYYYY " << num.size() << endl;
		for (int i = 0; i < m-1; i++) {
			//~ cout << m << " " << i << endl;
			int tmp = 0; //ans for now
			auto [tot, a, b] = num[i];
			//remove from right
			if (a <= rmed) {
				rsmall.erase(rsmall.find(a));
				rsmallsum -= a;
			} else {
				rbig.erase(rbig.find(a));
				rbigsum -= a;
			}
			if (b <= rmed) {
				rsmall.erase(rsmall.find(b));
				rsmallsum -= b;
			} else {
				rbig.erase(rbig.find(b));
				rbigsum -= b;
			}
			//equalize right array lengths
			if (rbig.size() > rsmall.size()) {
				auto it = rbig.begin();
				rsmall.insert(*it);
				rbigsum -= *it;
				rsmallsum += *it;
				rbig.erase(rbig.begin());
			} 
			if (rsmall.size() > rbig.size()) {
				auto it = rsmall.end(); it--;
				rbig.insert(*it);
				rbigsum += *it;
				rsmallsum -= *it;
				rsmall.erase(it);
			}
			auto it = rsmall.end(); it--;
			int rmed = *it;
			//~ cout << "R DONE" << endl;
			//add to left
			if (a <= lmed) {
				lsmall.insert(a);
				lsmallsum += a;
			} else {
				lbig.insert(a);
				lbigsum += a;
			}
			if (b <= rmed) {
				lsmall.insert(b);
				lsmallsum += b;
			}
			else {
				lbig.insert(b);
				lbigsum += b;
			}
			//equalize left array lengths
			if (lbig.size() > lsmall.size()) {
				auto it = lbig.begin();
				lsmall.insert(*it);
				lsmallsum += *it;
				lbigsum -= *it;
				lbig.erase(it);
			}
			if (lsmall.size() > lbig.size()) {
				auto it = lsmall.end(); it--;
				lbig.insert(*it);
				lbigsum += *it;
				lsmallsum -= *it;
				lsmall.erase(it);
			}
			//calc left median
			it = lsmall.end(); it--;
			lmed = *it;
			//~ cout << "L DONE" << endl;
			//calc left sum
			tmp += abs(lbigsum-lsmallsum);
			//~ cout << lmed << ": " << tmp;
			//calc right sum
			tmp += abs(rbigsum-rsmallsum);
			//update ans
			res = min(res, tmp);
			//~ cout << " AAA " << rmed << ": " << tmp << endl;
		}
		cout << res+ans << endl;
	}
}

//change if to while if wa as may be multiple??
//changes infinities higher if wa

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:45:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for (int i = 0; i < all.size(); i++) {
      |                   ~~^~~~~~~~~~~~
bridge.cpp:46:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |    if (i <= all.size()/2) {
      |        ~~^~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 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 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 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 0 ms 536 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 18 ms 5464 KB Output is correct
13 Correct 33 ms 6752 KB Output is correct
14 Correct 26 ms 5972 KB Output is correct
15 Correct 20 ms 4208 KB Output is correct
16 Correct 22 ms 6028 KB Output is correct
17 Correct 23 ms 6740 KB Output is correct
18 Correct 26 ms 6216 KB Output is correct
19 Correct 33 ms 6644 KB Output is correct
20 Correct 21 ms 6228 KB Output is correct
21 Correct 29 ms 6484 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 360 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -