Submission #587455

#	Time	Username	Problem	Language	Result	Execution time	Memory
587455		NekoRolly	Best Place (NOI17_bestplace)	C++17	100 / 100	44 ms	5392 KiB

bestplace

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+4;

int n,ansA,ansB;
ll a[N],b[N],prA[N],prB[N];

ll valA(int i){
	return (a[i]*(i-1) - prA[i-1]) + (prA[n]-prA[i] - a[i]*(n-i));
}

ll valB(int i){
	return (b[i]*(i-1) - prB[i-1]) + (prB[n]-prB[i] - b[i]*(n-i));
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n;

	for (int i=1; i<=n; i++) cin >> a[i] >> b[i];

	sort(a+1, a+n+1), sort(b+1, b+n+1);

	for (int i=1; i<=n; i++){
		prA[i] = prA[i-1] + a[i];
		prB[i] = prB[i-1] + b[i];
	}

	ansA = ansB = 1;
	for (int i=1; i<=n; i++){
		if (valA(ansA) > valA(i)) ansA = i;
		if (valB(ansB) > valB(i)) ansB = i;
	}

	cout << a[ansA] << " " << b[ansB] << "\n";

	return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 20 / 20
• Subtask 3: 28 / 28
• Subtask 4: 13 / 13
• Subtask 5: 17 / 17
• Subtask 6: 19 / 19