Submission #378701

#	Time	Username	Problem	Language	Result	Execution time	Memory
378701		Kevin_Zhang_TW	Chessboard (IZhO18_chessboard)	C++17	39 / 100	213 ms	2300 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(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 debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010;

int n, k;
vector<tuple<int,int,int,int>> subr;

ll calgood(int w, int x1, int y1, int x2, int y2) {

	ll res = 0;
	for (int i = x1;i <= x2;++i)
		for (int j = y1;j <= y2;++j) {
			int need = (1^(i/w) ^ (j/w))&1;
			res += need;
		}
	return res;

}
ll calcost(int wid) {
	ll res = calgood(wid, 0, 0, n-1, n-1);
	for (auto [x1, y1, x2, y2] : subr) {
		ll area = 1ll * (x2-x1+1) * (y2-y1+1);
		ll good = calgood(wid, x1, y1, x2, y2);
		ll bad = area - good;
		res -= good;
		res += bad;
	}

	return min(res, 1ll * n * n - res);
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> k;
	DE(n, k);

	if (n > 1000) return -1;
	subr.resize(k);
	for (auto &[x1, y1, x2, y2] : subr)
		cin >> x1 >> y1 >> x2 >> y2, --x1, --x2, --y1, --y2;

	ll res = 1ll * n * n;

	for (int i = 1;i < n;++i)
		if (n % i == 0)
			chmin(res, calcost(i));

	cout << res << '\n';
}

Compilation message (stderr)

chessboard.cpp: In function 'int32_t main()':
chessboard.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
chessboard.cpp:49:2: note: in expansion of macro 'DE'
   49 |  DE(n, k);
      |  ^~

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