Submission #14386

#	Time	Username	Problem	Language	Result	Execution time	Memory
14386		woqja125	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	109 ms	5996 KiB

bridge

#include<stdio.h>
#include<queue>
#include<algorithm>
#include<vector>
long long abs(long long x){return x>0?x:-x;}
void solve1();
void solve2();

struct person
{
	int l, r;
};
bool operator<(const person &A, const person &B){return A.l+A.r<B.l+B.r;}

int k, N=0;
long long ans=0;
person l[100001];
int main()
{
	int i, n;
	scanf("%d%d", &k, &n);
	char a[10], b[10];
	int aa, bb;
	for(i=1; i<=n; i++)
	{
		scanf("%s%d%s%d", a, &aa, b, &bb);
		ans += abs(aa-bb);
		if(a[0] != b[0])
		{
			N++;
			l[N].l = aa>bb?bb:aa;
			l[N].r = aa<bb?bb:aa;
			ans++;
		}
	}
	if(k==1) solve1();
	else solve2();
	printf("%lld\n", ans);
	return 0;
}

struct lineSet
{
	std::priority_queue<int> l;
	std::priority_queue<int, std::vector<int>, std::greater<int> > r;
	long long ans=0;
	void add(int ll, int rl);
};

void solve1()
{
	lineSet T;
	for(int i=1; i<=N; i++)
	{
		T.add(l[i].l, l[i].r);
	}
	ans += T.ans;
}

long long dp1[100010], dp2[100010];
void solve2()
{
	int i;
	std::sort(l+1, l+1+N);
	lineSet L, R;
	for(i=1; i<=N; i++)
	{
		L.add(l[i].l, l[i].r);
		dp1[i] = L.ans;
	}
	for(i=N; i>=1; i--)
	{
		R.add(l[i].l, l[i].r);
		dp2[i] = R.ans;
	}
	long long min = dp2[1];
	for(i=1; i<=N; i++)
	{
		if(min > dp1[i] + dp2[i+1]) min = dp1[i] + dp2[i+1];
	}
	ans += min;
}

void lineSet::add(int ll, int rl)
{
	l.push(ll); r.push(rl);
//	printf("##%d %d\n", ll, rl);
	while(1)
	{
		ll = l.top();
		rl = r.top();
//		printf("#%d %d\n", ll, rl);
		if(ll<=rl) return;
		l.pop(); r.pop();
		this->ans += (ll-rl)*2;
		l.push(rl); r.push(ll);
	}
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:21:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &k, &n);
                       ^
bridge.cpp:26:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%d%s%d", a, &aa, b, &bb);
                                    ^

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