Submission #810562

#	Time	Username	Problem	Language	Result	Execution time	Memory
810562		AkramElOmrani	Ideal city (IOI12_city)	C++17	23 / 100	23 ms	3156 KiB

city

#include <bits/stdc++.h>
using namespace std;
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
 
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);

#define ll long long
const int mod = 1e9;
int add(int a, int b) {
  a += b;
  if(a > mod) {
	a -= mod;
  }
  return a;
}
int mul(int a, int b) {
	a = (ll)a * b % mod;
	return a;
}
int sub(int a, int b) {
	a -= b;
	if(a < 0) {
		a += mod;
	}
	return a;
}
vector<pair<int, int>> dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
 
int DistanceSum(int n, int *X, int *Y) {
	// ans = sum(abs(x[i] - x[j])) + sum(abs(y[i] - y[j])) treat cases
	vector<int> x;
	int suff_x = 0;
	for(int i = 0; i < n; ++i) {
		x.push_back(X[i]);
		suff_x = add(suff_x, X[i]);
	}
	int suff_y = 0;
	vector<int> y;
	for(int i = 0; i < n; ++i) {
		y.push_back(Y[i]);
		suff_y = add(suff_y, Y[i]);
	}
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());

	int ans = 0;
	for(int i = 0; i < n; ++i) {
		ans = add(ans, sub(suff_x,  mul((n - i), x[i])));
		suff_x = sub(suff_x, x[i]);

		ans = add(ans, sub(suff_y,  mul((n - i), y[i])));
		suff_y = sub(suff_y, y[i]);
	}
	return ans;
}

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