#include <bits/stdc++.h>
#define pb push_back
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(data) data.begin() , data.end()
#define endl '\n'
//freopen("nenokku_easy.in", "r", stdin);
//freopen("nenokku_easy.out", "w", stdout);
#define int long long
using namespace std;
typedef long long ll;
const ll N = 1e3 + 5;
int n, k, pref[N][N];
main() {
cin >> n >> k;
for(int kk = 1; kk <= k; kk++) {
int x, y, xx, yy;
cin >> x >> y >> xx >> yy;
for(int i = x; i <= xx; i++) {
for(int j = y; j <= yy; j++) {
pref[i][j] = 1;
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
pref[i][j] += pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
}
}
int ans = n * n;
for(int z = 1; z <= (n >> 1); z++) {
if(n % z == 0) {
bool type = 1;
int res1 = 0, res2 = 0;
for(int i = z; i <= n; i += z) {
for(int j = z; j <= n; j += z) {
if(type) {
res1 += pref[i][j] - pref[i][j - z] - pref[i - z][j] + pref[i - z][j - z];
res2 += z * z - (pref[i][j] - pref[i][j - z] - pref[i - z][j] + pref[i - z][j - z]);
} else {
res1 += z * z - (pref[i][j] - pref[i][j - z] - pref[i - z][j] + pref[i - z][j - z]);
res2 += pref[i][j] - pref[i][j - z] - pref[i - z][j] + pref[i - z][j - z];
}
type = 1 - type;
}
}
ans = min(ans, min(res1, res2));
}
}
cout << ans;
}
/*
5
2 8 5 1 10
5
2 3 5 3
2 5 3 3
1 4 4
2 3 4 2
1 1 2
*/
Compilation message
chessboard.cpp:17:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
17 | main() {
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
288 KB |
Output is correct |
2 |
Correct |
1 ms |
716 KB |
Output is correct |
3 |
Correct |
1 ms |
716 KB |
Output is correct |
4 |
Correct |
1 ms |
716 KB |
Output is correct |
5 |
Correct |
1 ms |
716 KB |
Output is correct |
6 |
Correct |
1 ms |
684 KB |
Output is correct |
7 |
Correct |
1 ms |
716 KB |
Output is correct |
8 |
Correct |
1 ms |
716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
1 ms |
588 KB |
Output is correct |
3 |
Correct |
1 ms |
588 KB |
Output is correct |
4 |
Correct |
1 ms |
588 KB |
Output is correct |
5 |
Correct |
1 ms |
588 KB |
Output is correct |
6 |
Incorrect |
1 ms |
588 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
1 ms |
588 KB |
Output is correct |
3 |
Correct |
1 ms |
588 KB |
Output is correct |
4 |
Correct |
1 ms |
588 KB |
Output is correct |
5 |
Correct |
1 ms |
588 KB |
Output is correct |
6 |
Incorrect |
1 ms |
588 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
288 KB |
Output is correct |
2 |
Correct |
1 ms |
716 KB |
Output is correct |
3 |
Correct |
1 ms |
716 KB |
Output is correct |
4 |
Correct |
1 ms |
716 KB |
Output is correct |
5 |
Correct |
1 ms |
716 KB |
Output is correct |
6 |
Correct |
1 ms |
684 KB |
Output is correct |
7 |
Correct |
1 ms |
716 KB |
Output is correct |
8 |
Correct |
1 ms |
716 KB |
Output is correct |
9 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
10 |
Halted |
0 ms |
0 KB |
- |