Submission #40579

#	Time	Username	Problem	Language	Result	Execution time	Memory
40579		Waschbar	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	494 ms	53800 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);
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:52:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &k, &n);
                        ^
bridge.cpp:57:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   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