Submission #118551

#	Time	Username	Problem	Language	Result	Execution time	Memory
118551		roseanne_pcy	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	100 ms	6124 KiB

bridge

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxn = 1e5+5;

int k, n;

ii foo[maxn];
ll base = 0;

bool cmp(ii a, ii b)
{
	return a.X+a.Y< b.X+b.Y;
}

ll v1[maxn], v2[maxn];

priority_queue<int> pq1;
priority_queue<int, vector<int>, greater<int> > pq2;
ll s1 = 0, s2 = 0;

void proc(int x)
{
	if(pq1.empty() && pq2.empty())
	{
		pq1.push(x);
		s1 += x;
	}
	else if(pq1.empty())
	{
		if(x< pq2.top()) pq1.push(x), s1 += x;
		else pq2.push(x), s2 += x;
	}
	else
	{
		if(x> pq1.top()) pq2.push(x), s2 += x;
		else pq1.push(x), s1 += x;
	}
}

void adjust()
{
	if(pq1.size() == pq2.size()) return;
	if(pq1.size()> pq2.size())
	{
		int x = pq1.top(); pq1.pop();
		s1 -= x;
		pq2.push(x); s2 += x;
	}
	else
	{
		int x = pq2.top(); pq2.pop();
		s2 -= x;
		pq1.push(x); s1 += x;
	}
}

int main()
{
	scanf("%d %d", &k, &n);
	int m = 0;
	for(int i = 1; i<= n; i++)
	{
		char a, b;
		int x, y;
		scanf(" %c %d %c %d", &a, &x, &b, &y);
		if(a == b)
		{
			base += abs(x-y);
			continue;
		}
		if(abs(x)> abs(y)) swap(x, y);
		m++;
		foo[m] = {x, y};
	}
	n = m;
	sort(foo+1, foo+n+1, cmp);
	for(int i = 1; i<= n; i++)
	{
		int x = foo[i].X, y = foo[i].Y;
		proc(x); proc(y);
		adjust();
		v1[i] = s2-s1;
	}
	while(!pq1.empty()) pq1.pop(); s1 = 0;
	while(!pq2.empty()) pq2.pop(); s2 = 0;
	for(int i = n; i>= 1; i--)
	{
		int x = foo[i].X, y = foo[i].Y;
		proc(x); proc(y);
		adjust();
		v2[i] = s2-s1;
	}
	ll best = 1e18;
	if(k == 1) best = v1[n];
	else
	{
		best = min(v1[n], v2[1]);
		for(int i = 1; i<= n; i++)
		{
			best = min(best, v1[i]+v2[i+1]);
		}
	}
	printf("%lld\n", best+base+n);
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:92:2: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  while(!pq1.empty()) pq1.pop(); s1 = 0;
  ^~~~~
bridge.cpp:92:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  while(!pq1.empty()) pq1.pop(); s1 = 0;
                                 ^~
bridge.cpp:93:2: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  while(!pq2.empty()) pq2.pop(); s2 = 0;
  ^~~~~
bridge.cpp:93:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  while(!pq2.empty()) pq2.pop(); s2 = 0;
                                 ^~
bridge.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &k, &n);
  ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %d %c %d", &a, &x, &b, &y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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