Submission #551892

#	Time	Username	Problem	Language	Result	Execution time	Memory
551892		sidon	Chessboard (IZhO18_chessboard)	C++17	100 / 100	388 ms	1832 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t

int32_t main() {
	int N, K; cin >> N >> K;
	ll ans = ll(N) * N;

	array<int, 4> a[K];
	for(auto &[i, j, k, l] : a)
		cin >> i >> j >> k >> l;

	for(int s = 1; s < N; ++s) if(!(N % s)) {

#define c(V) (s * ((V) / (2 * s)) + min(s, (V) % (2 * s)))

		ll cost = ll(c(N)) * (N - c(N)) + ll(c(N)) * (N - c(N));

		for(auto [i, j, k, l] : a) {
			ll u = k - i + 1, x = c(k) - c(i - 1);
			ll v = l - j + 1, y = c(l) - c(j - 1);

			cost += 2 * (x * y + (u - x) * (v - y)) - u * v;
		}
		ans = min(ans, min(cost, ll(N) * N - cost));
	}
	cout << ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 23 / 23
• Subtask 6: 30 / 30