Submission #879730

#TimeUsernameProblemLanguageResultExecution timeMemory
879730NeroZeinIdeal city (IOI12_city)C++17
0 / 100
3 ms604 KiB
#include "bits/stdc++.h" using namespace std; const int md = (int) 1e9; int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; int DistanceSum(int N, int *X, int *Y) { int ret = 0; int mxn = 0, mxm = 0; int mnn = INT_MAX, mnm = INT_MAX; for (int i = 0; i < N; ++i) { mxn = max(mxn, X[i]); mxm = max(mxm, Y[i]); mnn = min(mnn, X[i]); mnm = min(mnm, Y[i]); } auto sum = [&](int r) { return (int) (((long long) r * (r + 1) / 2) % md); }; auto mul = [&](int x, int y) { return (int) ((long long) x * y % md); }; auto add = [&](int& x, int y) { x += y; if (x >= md) x -= md; }; int lenn = mxn - mnn + 1; int lenm = mxm - mnm + 1; for (int i = 0; i < N; ++i) { int x = X[i], y = Y[i]; int sx = mul(sum(x - mnn), lenm); //add(sx, mul(sum(mxn - x), lenm)); int sy = mul(sum(y - mnm), lenn); //add(sy, mul(sum(mxm - y), lenn)); add(ret, sx); add(ret, sy); } return ret; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...