oj.uz

Submission #587455

# Submission time Handle Problem Language Result Execution time Memory
587455 2022-07-01T22:05:51 Z NekoRolly Best Place (NOI17_bestplace) C++17
100 / 100
 44 ms 5392 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3356 KB Output is correct
2 Correct 22 ms 3412 KB Output is correct
3 Correct 31 ms 4548 KB Output is correct
4 Correct 26 ms 4480 KB Output is correct
5 Correct 21 ms 4564 KB Output is correct
6 Correct 22 ms 4512 KB Output is correct
7 Correct 29 ms 4428 KB Output is correct
8 Correct 23 ms 4556 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #6
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3396 KB Output is correct
2 Correct 35 ms 5320 KB Output is correct
3 Correct 25 ms 5392 KB Output is correct
4 Correct 30 ms 4652 KB Output is correct
5 Correct 35 ms 5352 KB Output is correct
6 Correct 44 ms 5384 KB Output is correct
7 Correct 33 ms 5352 KB Output is correct
8 Correct 34 ms 5324 KB Output is correct