제출 #378519

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
378519		casperwang	Chessboard (IZhO18_chessboard)	C++14	70 / 100	2062 ms	748 KiB

chessboard

#include <bits/stdc++.h>
#define int long long
#define pb emplace_back
#define y1 y_1
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }

const int MAXN = 100000;
int N, K;
int x1, y1, x2, y2;
vector <int> fac;
vector <vector<int>> c;
int cnt, ans;

void init() {
	for (int i = 1; i < N; i++)
		if (N % i == 0) fac.pb(i);
	c.resize(fac.size());
	for (vector <int> &v : c)
		v.resize(2);
}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N >> K;
	init();
	for (int i = 0; i < K; i++) {
		cin >> x1 >> y1 >> x2 >> y2;
		for (int x = x1; x <= x2; x++) {
			for (int y = y1; y <= y2; y++) {
				int id = 0;
				for (int p : fac) {
					int t = ((x+p-1) / p) + ((y+p-1) / p);
					c[id++][t & 1]++, cnt++;
				}
			}
		}
	}
	ans = N * N;
	cnt /= fac.size();
	int id = 0;
	for (int p : fac) {
		int m1 = (N / p) * (N / p) / 2 * p * p;
		int m0 = N * N - m1;
		// debug(p, m0, m1);
		// debug(m1 - c[id][1] + c[id][0]);
		// debug(m0 - c[id][0] + c[id][1]);
		ans = min(ans, m1 - c[id][1] + c[id][0]);
		ans = min(ans, m0 - c[id][0] + c[id][1]);
		id++;
	}
	cout << ans << '\n';
}

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