//
// main.cpp
// torelax
//
// Created by Rakhman on 11/15/20.
//
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>
#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define no_answer {cout << "NO"; exit(0);}
#define FOR(i, start, finish, k) for(llong i = start; i <= finish; i += k)
const long long mxn = 1e5 + 110;
const long long mnn = 1e3 + 2;
const long long mod = 1e9 + 7;
const long long inf = 1e18;
const long long OO = 1e9;
typedef long long llong;
typedef unsigned long long ullong;
using namespace std;
llong n, k;
llong ans = inf;
struct dot{
llong left, up, right, down;
}b[mxn];
llong get_color(llong x, llong y, llong d){
return (((x - 1) / d) + ((y - 1) / d)) % 2;
}
llong get(llong d){
//left-corner is black
llong blacks = d * d * (n / d) * (n / d / 2);
if((n / d) % 2 == 1){
blacks += d * d * (n / d / 2 + 1);
}
llong paint = 0;
llong blacks1 = n * n - blacks;
for(int i = 1; i <= k; i++){
int x = b[i].left, y = b[i].up;
if(get_color(x, y, d) == 0){
blacks--;
}else{
paint++;
}
}
//left-corner is white
llong paint1 = 0;
for(int i = 1; i <= k; i++){
int x = b[i].left, y = b[i].up;
if(get_color(x, y, d) == 1){
blacks1--;
}else{
paint1++;
}
}
return min(blacks1 + paint1, blacks + paint);
}
int main() {
ios;
cin >> n >> k;
for(int i = 1; i <= k; i++){
cin >> b[i].left >> b[i].up >> b[i].right >> b[i].down;
}
for(int i = 1; i <= sqrt(n); i++){
if(n % i == 0){
ans = min(ans, get(i));
if(n / i != i && i != 1){
ans = min(get(n / i), ans);
}
}
}
cout << ans;
}
/*
6 8
3 3 3 3
1 2 1 2
3 4 3 4
5 5 5 5
4 3 4 3
4 4 4 4
2 1 2 1
3 6 3 6
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
0 ms |
364 KB |
Output is correct |
4 |
Correct |
0 ms |
364 KB |
Output is correct |
5 |
Correct |
0 ms |
364 KB |
Output is correct |
6 |
Correct |
0 ms |
364 KB |
Output is correct |
7 |
Correct |
0 ms |
364 KB |
Output is correct |
8 |
Correct |
0 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
2284 KB |
Output is correct |
2 |
Correct |
7 ms |
876 KB |
Output is correct |
3 |
Correct |
16 ms |
1516 KB |
Output is correct |
4 |
Correct |
21 ms |
1772 KB |
Output is correct |
5 |
Correct |
23 ms |
2028 KB |
Output is correct |
6 |
Correct |
14 ms |
1388 KB |
Output is correct |
7 |
Correct |
4 ms |
620 KB |
Output is correct |
8 |
Correct |
17 ms |
1388 KB |
Output is correct |
9 |
Correct |
37 ms |
3436 KB |
Output is correct |
10 |
Correct |
20 ms |
1900 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
0 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
0 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
12 ms |
1260 KB |
Output is correct |
17 |
Correct |
29 ms |
2924 KB |
Output is correct |
18 |
Correct |
42 ms |
3444 KB |
Output is correct |
19 |
Correct |
105 ms |
3164 KB |
Output is correct |
20 |
Correct |
120 ms |
3436 KB |
Output is correct |
21 |
Correct |
29 ms |
2924 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
24 ms |
1644 KB |
Output is correct |
24 |
Correct |
38 ms |
3180 KB |
Output is correct |
25 |
Correct |
5 ms |
620 KB |
Output is correct |
26 |
Correct |
24 ms |
2156 KB |
Output is correct |
27 |
Correct |
33 ms |
2412 KB |
Output is correct |
28 |
Correct |
39 ms |
3308 KB |
Output is correct |
29 |
Correct |
12 ms |
1388 KB |
Output is correct |
30 |
Correct |
2 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
2284 KB |
Output is correct |
2 |
Correct |
7 ms |
876 KB |
Output is correct |
3 |
Correct |
16 ms |
1516 KB |
Output is correct |
4 |
Correct |
21 ms |
1772 KB |
Output is correct |
5 |
Correct |
23 ms |
2028 KB |
Output is correct |
6 |
Correct |
14 ms |
1388 KB |
Output is correct |
7 |
Correct |
4 ms |
620 KB |
Output is correct |
8 |
Correct |
17 ms |
1388 KB |
Output is correct |
9 |
Correct |
37 ms |
3436 KB |
Output is correct |
10 |
Correct |
20 ms |
1900 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
0 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
12 ms |
1260 KB |
Output is correct |
27 |
Correct |
29 ms |
2924 KB |
Output is correct |
28 |
Correct |
42 ms |
3444 KB |
Output is correct |
29 |
Correct |
105 ms |
3164 KB |
Output is correct |
30 |
Correct |
120 ms |
3436 KB |
Output is correct |
31 |
Correct |
29 ms |
2924 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
24 ms |
1644 KB |
Output is correct |
34 |
Correct |
38 ms |
3180 KB |
Output is correct |
35 |
Correct |
5 ms |
620 KB |
Output is correct |
36 |
Correct |
24 ms |
2156 KB |
Output is correct |
37 |
Correct |
33 ms |
2412 KB |
Output is correct |
38 |
Correct |
39 ms |
3308 KB |
Output is correct |
39 |
Correct |
12 ms |
1388 KB |
Output is correct |
40 |
Correct |
2 ms |
364 KB |
Output is correct |
41 |
Correct |
101 ms |
2924 KB |
Output is correct |
42 |
Correct |
44 ms |
3308 KB |
Output is correct |
43 |
Correct |
63 ms |
2924 KB |
Output is correct |
44 |
Correct |
43 ms |
3180 KB |
Output is correct |
45 |
Correct |
39 ms |
3436 KB |
Output is correct |
46 |
Correct |
116 ms |
3328 KB |
Output is correct |
47 |
Correct |
35 ms |
3052 KB |
Output is correct |
48 |
Correct |
53 ms |
3052 KB |
Output is correct |
49 |
Correct |
39 ms |
2924 KB |
Output is correct |
50 |
Correct |
446 ms |
3308 KB |
Output is correct |
51 |
Correct |
472 ms |
3308 KB |
Output is correct |
52 |
Correct |
436 ms |
3328 KB |
Output is correct |
53 |
Correct |
464 ms |
3308 KB |
Output is correct |
54 |
Correct |
429 ms |
3052 KB |
Output is correct |
55 |
Correct |
487 ms |
3564 KB |
Output is correct |
56 |
Correct |
417 ms |
3092 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
0 ms |
364 KB |
Output is correct |
4 |
Correct |
0 ms |
364 KB |
Output is correct |
5 |
Correct |
0 ms |
364 KB |
Output is correct |
6 |
Correct |
0 ms |
364 KB |
Output is correct |
7 |
Correct |
0 ms |
364 KB |
Output is correct |
8 |
Correct |
0 ms |
364 KB |
Output is correct |
9 |
Correct |
26 ms |
2284 KB |
Output is correct |
10 |
Correct |
7 ms |
876 KB |
Output is correct |
11 |
Correct |
16 ms |
1516 KB |
Output is correct |
12 |
Correct |
21 ms |
1772 KB |
Output is correct |
13 |
Correct |
23 ms |
2028 KB |
Output is correct |
14 |
Correct |
14 ms |
1388 KB |
Output is correct |
15 |
Correct |
4 ms |
620 KB |
Output is correct |
16 |
Correct |
17 ms |
1388 KB |
Output is correct |
17 |
Correct |
37 ms |
3436 KB |
Output is correct |
18 |
Correct |
20 ms |
1900 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
1 ms |
364 KB |
Output is correct |
27 |
Correct |
1 ms |
364 KB |
Output is correct |
28 |
Correct |
0 ms |
364 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
1 ms |
364 KB |
Output is correct |
31 |
Correct |
1 ms |
364 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
1 ms |
364 KB |
Output is correct |
34 |
Correct |
12 ms |
1260 KB |
Output is correct |
35 |
Correct |
29 ms |
2924 KB |
Output is correct |
36 |
Correct |
42 ms |
3444 KB |
Output is correct |
37 |
Correct |
105 ms |
3164 KB |
Output is correct |
38 |
Correct |
120 ms |
3436 KB |
Output is correct |
39 |
Correct |
29 ms |
2924 KB |
Output is correct |
40 |
Correct |
1 ms |
364 KB |
Output is correct |
41 |
Correct |
24 ms |
1644 KB |
Output is correct |
42 |
Correct |
38 ms |
3180 KB |
Output is correct |
43 |
Correct |
5 ms |
620 KB |
Output is correct |
44 |
Correct |
24 ms |
2156 KB |
Output is correct |
45 |
Correct |
33 ms |
2412 KB |
Output is correct |
46 |
Correct |
39 ms |
3308 KB |
Output is correct |
47 |
Correct |
12 ms |
1388 KB |
Output is correct |
48 |
Correct |
2 ms |
364 KB |
Output is correct |
49 |
Correct |
101 ms |
2924 KB |
Output is correct |
50 |
Correct |
44 ms |
3308 KB |
Output is correct |
51 |
Correct |
63 ms |
2924 KB |
Output is correct |
52 |
Correct |
43 ms |
3180 KB |
Output is correct |
53 |
Correct |
39 ms |
3436 KB |
Output is correct |
54 |
Correct |
116 ms |
3328 KB |
Output is correct |
55 |
Correct |
35 ms |
3052 KB |
Output is correct |
56 |
Correct |
53 ms |
3052 KB |
Output is correct |
57 |
Correct |
39 ms |
2924 KB |
Output is correct |
58 |
Correct |
446 ms |
3308 KB |
Output is correct |
59 |
Correct |
472 ms |
3308 KB |
Output is correct |
60 |
Correct |
436 ms |
3328 KB |
Output is correct |
61 |
Correct |
464 ms |
3308 KB |
Output is correct |
62 |
Correct |
429 ms |
3052 KB |
Output is correct |
63 |
Correct |
487 ms |
3564 KB |
Output is correct |
64 |
Correct |
417 ms |
3092 KB |
Output is correct |
65 |
Correct |
0 ms |
364 KB |
Output is correct |
66 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
67 |
Halted |
0 ms |
0 KB |
- |