제출 #942982

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
942982		oblantis	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	206 ms	14460 KiB

bridge

#include <bits/stdc++.h>

using namespace std; 

#define mp make_pair
typedef pair<int, int> pii;

vector<int> points;
long long easy;
long long ans;
long long lt[110000];
long long rt[110000];
int n, k;
vector< pii > bridge;

bool compara(pii a, pii b) {
	return a.first + a.second < b.first + b.second;
}

template<class T> 
void calc(T it, T ed, long long *arr) {
	multiset<int> sm;
	multiset<int> bg;

	long long ssm = 0;
	long long sbg = 0;

	int c = 0;
	arr[c++] = 0;

	while (it != ed) {
		sm.insert(it->first);
		ssm += it->first;
		bg.insert(it->second);
		sbg += it->second;

		while (*sm.rbegin() > *bg.begin()) {
			sbg += *sm.rbegin() - *bg.begin();
			ssm += *bg.begin() - *sm.rbegin();
			bg.insert(*sm.rbegin());
			sm.insert(*bg.begin());
			bg.erase(bg.begin());
			sm.erase(--sm.end());
		}

		arr[c++] = sbg - ssm;
		it++;
	}
}

int main() {
	scanf("%d %d", &k, &n);

	for (int i = 0; i < n; i++) {
		char t1, t2;
		int x, y;
		scanf(" %c %d %c %d", &t1, &x, &t2, &y);
		if (t1 == t2) easy += abs(y-x);
		else bridge.push_back(mp(x, y));
	}

	sort(bridge.begin(), bridge.end(), compara);
	
	calc(bridge.begin(), bridge.end(), lt); // prefixes
	calc(bridge.rbegin(), bridge.rend(), rt); // suffixes

	n = bridge.size();

	if (k == 1) {
		ans = rt[n];
	}
	else {
		ans = 1000000000000000000LL;
		for (int in_lt = 0; in_lt <= n; in_lt++) {
			ans = min(ans, lt[in_lt] + rt[n - in_lt]);
		}
	}

	printf("%lld\n", easy + ans + n);
}

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'int main()':
bridge.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  scanf("%d %d", &k, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf(" %c %d %c %d", &t1, &x, &t2, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37