제출 #251546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
251546		kostia244	Ideal city (IOI12_city)	C++17	0 / 100	6 ms	640 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(i) sum += (cx[i-1])*1ll*X[i];
		sum -= (n-cx[i])*1ll*X[i];
		if(i) sum += (cy[i-1])*1ll*Y[i];
		sum -= (n-cy[i])*1ll*Y[i];
	}
	return sum%1000000000;
}

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