Submission #251551

#	Time	Username	Problem	Language	Result	Execution time	Memory
251551		kostia244	Ideal city (IOI12_city)	C++17	23 / 100	29 ms	2808 KiB

city

#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
const int maxn = 1<<18;
int cx[maxn], cy[maxn];
int DistanceSum(int n, int *X, int *Y) {
	ll sum = 0;
	int minx = 1<<30, miny = 1<<30;
	for(int i = 0; i < n; i++) {
		minx = min(minx, X[i]),
		miny = min(miny, Y[i]);
	}
	for(int i = 0; i < n; i++) {
		X[i] -= minx, Y[i] -= miny;
		cx[X[i]]++, cy[Y[i]]++;
	}
	for(int i = 1; i < n; i++) cx[i] += cx[i-1];
	for(int i = 1; i < n; i++) cy[i] += cy[i-1];
	for(int i = 0; i < n; i++) {
		if(X[i]) sum += (cx[X[i]-1])*1ll*X[i];
		sum -= (n-cx[X[i]])*1ll*X[i];
		if(Y[i]) sum += (cy[Y[i]-1])*1ll*Y[i];
		sum -= (n-cy[Y[i]])*1ll*Y[i];
	}
	return sum%1000000000;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 21
• Subtask 3: 23 / 23
• Subtask 4: 0 / 45