Submission #77032

#	Time	Username	Problem	Language	Result	Execution time	Memory
77032		vex	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	73 ms	21176 KiB

bridge

#include<bits/stdc++.h>
#define maxn 200005
using namespace std;

int n,k;
int a[maxn];
long long s[maxn];
long long sol=0;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	cin>>k>>n;
	int br=1;
	for(int i=0;i<n;i++)
	{
		char h,j;
		int x,y;
		cin>>h>>x>>j>>y;
		
		if(h==j)sol+=abs(x-y);
		else{
			a[br]=x;
			br++;
			a[br]=y;
			br++;
		}
	}
	n=br;
	
	sort(a+1,a+n);
	s[0]=0LL;
	for(int i=1;i<n;i++)s[i]=s[i-1]+a[i];
	
	if(k==1)
	{
		int mo=a[n/2];
		cout<<sol + 1LL*mo*(n/2 - 1)-s[n/2 - 1] + s[n-1]-s[n/2]-1LL*mo*(n-1-n/2) + (n-1)/2<<endl;
		return 0;
	}
	return 0;
}

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