| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 855836 | Trisanu_Das | Chessboard (IZhO18_chessboard) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
#define int long long
const int maxn = 100004;
int n, k, tot, x1[maxn], y1[maxn], x2[maxn], y2[maxn];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> k;
for (int i = 0; i < k; i++) {
cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
x1[i]--; y1[i]--; x2[i]--; y2[i]--;
tot += (x2[i] - x1[i] + 1) * (y2[i] - y1[i] + 1);
}
int ans = LLONG_MAX;
for (int i = 1; i < n; i++)
if (n % i == 0) {
int t = 0, alt1 = ((n / i) * (n / i) + 1) / 2 * i * i, alt2 = ((n / i) * (n / i)) / 2 * i * i;
for (int j = 0; j < k; j++) if (((x1[j] / i) & 1) == ((y1[j] / i) & 1)) t++;
ans = min(ans, min((alt1 - t) + (tot - t), (alt2 - (tot - t)) + t));
}
cout << ans << '\n';
}