Submission #429675

#	Time	Username	Problem	Language	Result	Execution time	Memory
429675		Mounir	이상적인 도시 (IOI12_city)	C++14	0 / 100	7 ms	816 KiB

city

#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
#define pb push_back
#define all(x) x.begin(), x.end()
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
using namespace std;

const int MOD =  1000000000, N = 3000;
int delta[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool estVille[N][N], vue[N][N];
int dist[N][N];

int DistanceSum(int nVilles, int *X, int *Y) {
	vector<int> x, y;
	for (int iVille = 0; iVille < nVilles; ++iVille){
		x.pb(X[iVille]);
		y.pb(Y[iVille]);
	}

	int SUM  = 0;

	sort(all(x)); sort(all(y));
	int sumPg = 0, sumPp = 0;
	for (int e : x){
		sumPg = (sumPg + e)%MOD;
	}
	sumPg = (sumPg - x[0])%MOD;
	for (int ind = 0; ind < nVilles; ++ind){
		int add = (ind * x[ind] - sumPp)%MOD;
		add = (add + sumPg - (nVilles - 1 - ind) * x[ind])%MOD;

		SUM = (SUM + add)%MOD;
		if (ind != nVilles - 1){
			sumPg = (sumPg - x[ind + 1])%MOD;
		}
		sumPp = (sumPp + x[ind])%MOD;
	}

	//cout << "sum " << SUM << endl;

	sumPg = 0, sumPp = 0;
	for (int e :y)
		sumPg = (sumPg + e)%MOD;
	sumPg = (sumPg - y[0])%MOD;
	for (int ind = 0; ind < nVilles; ++ind){
		int add = (ind * y[ind] - sumPp)%MOD;
	//	cout << "add" << add << endl;

		add = (add + sumPg - (nVilles - 1 - ind) * y[ind])%MOD;

	//	cout << "add " << add << endl;

		SUM = (SUM + add)%MOD;
		if (ind != nVilles - 1){
			sumPg = (sumPg - y[ind + 1])%MOD;
		}
		sumPp = (sumPp + y[ind])%MOD;
	}
	return SUM/2;
}

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