// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii; typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define pb emplace_back
#define FOR(i,n) for(int i = 0; i < (n); ++i)
#define FOO(i,a,b) for(int i = (a); i <= (b); ++i)
#define AI(x) begin(x),end(x)
template<class I> bool chmax(I &a, I b){ return a < b ? (a = b, true) : false;}
template<class I> bool chmin(I &a, I b){ return a > b ? (a = b, true) : false;}
#ifdef OWO
#define debug(args...) LKJ("[ " + string(#args) + " ]", args)
void LKJ(){ cerr << endl;}
template<class I, class...T> void LKJ(I&&x, T&&...t){ cerr<<x<<", ", LKJ(t...);}
template<class I> void DE(I a, I b){ while(a < b) cerr << *a << " \n"[next(a) == b], ++a;}
#else
#define debug(...) 0
#define DE(...) 0
#endif
const int N = 1e5 + 1;
int n, k;
void findfac(int n, vector<int> &fac){
for(int i = 1; i * i <= n; ++i){
if(n % i != 0) continue;
fac.pb(i);
fac.pb(n / i);
}
sort(AI(fac));
fac.erase(unique(AI(fac)), end(fac));
if(fac.back() == n) fac.pop_back();
}
int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> k;
vector<int> facs;
findfac(n, facs);
// ca : has top left corner
// cb : does not
vector<ll> ca(facs.size());
vector<ll> cb(facs.size());
FOR(i,facs.size()){
int f = facs[i];
ll nn = n / f;
ll bc = (nn * nn + 1) / 2;
ca[i] = bc * f * f;
cb[i] = 1ll * n * n - ca[i];
}
FOR(_,k){
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
--x1, --y1, --x2, --y2;
FOR(i, facs.size()){
int f = facs[i];
int lx = x2 - x1 + 1;
int ly = y2 - y1 + 1;
lx %= f * 2, ly %= f * 2;
if(lx == 0 or ly == 0) continue;
int xx = x1 + lx - 1;
int yy = y1 + ly - 1;
int dx = x1 % f;
int dy = y1 % f;
ll v;
if(dx + lx - 1 < f and dy + ly - 1 < f){
v = lx * ly;
} else if(dx + lx - 1 < f){
v = 1ll * lx * ((f - dy) - (dy + ly - 1 - f));
} else if(dy + ly - 1 < f){
v = 1ll * ly * ((f - dx) - (dx + lx - 1 - f));
} else {
ll a = f - dx;
ll b = lx - a;
ll c = f - dy;
ll d = ly - c;
v = (a - b) * (c - d);
}
int x = x1 / f;
int y = y1 / f;
if((x + y) & 1) cb[i] -= v, ca[i] += v;
else ca[i] -= v, cb[i] += v;
}
}
DE(AI(facs));
DE(AI(ca));
DE(AI(cb));
cout << min(
*min_element(AI(ca)),
*min_element(AI(cb))
);
return 0;
}
Compilation message
chessboard.cpp: In function 'int32_t main()':
chessboard.cpp:9:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | #define FOR(i,n) for(int i = 0; i < (n); ++i)
| ^
chessboard.cpp:48:2: note: in expansion of macro 'FOR'
48 | FOR(i,facs.size()){
| ^~~
chessboard.cpp:9:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | #define FOR(i,n) for(int i = 0; i < (n); ++i)
| ^
chessboard.cpp:60:3: note: in expansion of macro 'FOR'
60 | FOR(i, facs.size()){
| ^~~
chessboard.cpp:68:8: warning: unused variable 'xx' [-Wunused-variable]
68 | int xx = x1 + lx - 1;
| ^~
chessboard.cpp:69:8: warning: unused variable 'yy' [-Wunused-variable]
69 | int yy = y1 + ly - 1;
| ^~
chessboard.cpp:21:17: warning: statement has no effect [-Wunused-value]
21 | #define DE(...) 0
| ^
chessboard.cpp:95:2: note: in expansion of macro 'DE'
95 | DE(AI(facs));
| ^~
chessboard.cpp:21:17: warning: statement has no effect [-Wunused-value]
21 | #define DE(...) 0
| ^
chessboard.cpp:96:2: note: in expansion of macro 'DE'
96 | DE(AI(ca));
| ^~
chessboard.cpp:21:17: warning: statement has no effect [-Wunused-value]
21 | #define DE(...) 0
| ^
chessboard.cpp:97:2: note: in expansion of macro 'DE'
97 | DE(AI(cb));
| ^~
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
364 KB |
Output is correct |
2 |
Correct |
7 ms |
364 KB |
Output is correct |
3 |
Correct |
15 ms |
364 KB |
Output is correct |
4 |
Correct |
17 ms |
364 KB |
Output is correct |
5 |
Correct |
21 ms |
364 KB |
Output is correct |
6 |
Correct |
14 ms |
364 KB |
Output is correct |
7 |
Correct |
3 ms |
364 KB |
Output is correct |
8 |
Correct |
13 ms |
364 KB |
Output is correct |
9 |
Correct |
35 ms |
364 KB |
Output is correct |
10 |
Correct |
19 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
1 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 |
# |
Verdict |
Execution time |
Memory |
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 |
1 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 |
11 ms |
364 KB |
Output is correct |
17 |
Correct |
32 ms |
384 KB |
Output is correct |
18 |
Correct |
40 ms |
364 KB |
Output is correct |
19 |
Correct |
92 ms |
392 KB |
Output is correct |
20 |
Correct |
105 ms |
492 KB |
Output is correct |
21 |
Correct |
31 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
21 ms |
364 KB |
Output is correct |
24 |
Correct |
34 ms |
364 KB |
Output is correct |
25 |
Correct |
6 ms |
364 KB |
Output is correct |
26 |
Correct |
22 ms |
364 KB |
Output is correct |
27 |
Correct |
30 ms |
364 KB |
Output is correct |
28 |
Correct |
36 ms |
492 KB |
Output is correct |
29 |
Correct |
11 ms |
364 KB |
Output is correct |
30 |
Correct |
2 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
364 KB |
Output is correct |
2 |
Correct |
7 ms |
364 KB |
Output is correct |
3 |
Correct |
15 ms |
364 KB |
Output is correct |
4 |
Correct |
17 ms |
364 KB |
Output is correct |
5 |
Correct |
21 ms |
364 KB |
Output is correct |
6 |
Correct |
14 ms |
364 KB |
Output is correct |
7 |
Correct |
3 ms |
364 KB |
Output is correct |
8 |
Correct |
13 ms |
364 KB |
Output is correct |
9 |
Correct |
35 ms |
364 KB |
Output is correct |
10 |
Correct |
19 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 |
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 |
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 |
11 ms |
364 KB |
Output is correct |
27 |
Correct |
32 ms |
384 KB |
Output is correct |
28 |
Correct |
40 ms |
364 KB |
Output is correct |
29 |
Correct |
92 ms |
392 KB |
Output is correct |
30 |
Correct |
105 ms |
492 KB |
Output is correct |
31 |
Correct |
31 ms |
364 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
21 ms |
364 KB |
Output is correct |
34 |
Correct |
34 ms |
364 KB |
Output is correct |
35 |
Correct |
6 ms |
364 KB |
Output is correct |
36 |
Correct |
22 ms |
364 KB |
Output is correct |
37 |
Correct |
30 ms |
364 KB |
Output is correct |
38 |
Correct |
36 ms |
492 KB |
Output is correct |
39 |
Correct |
11 ms |
364 KB |
Output is correct |
40 |
Correct |
2 ms |
364 KB |
Output is correct |
41 |
Correct |
84 ms |
364 KB |
Output is correct |
42 |
Correct |
42 ms |
492 KB |
Output is correct |
43 |
Correct |
57 ms |
364 KB |
Output is correct |
44 |
Correct |
41 ms |
364 KB |
Output is correct |
45 |
Correct |
37 ms |
364 KB |
Output is correct |
46 |
Correct |
94 ms |
364 KB |
Output is correct |
47 |
Correct |
32 ms |
364 KB |
Output is correct |
48 |
Correct |
48 ms |
492 KB |
Output is correct |
49 |
Correct |
44 ms |
364 KB |
Output is correct |
50 |
Correct |
364 ms |
364 KB |
Output is correct |
51 |
Correct |
393 ms |
492 KB |
Output is correct |
52 |
Correct |
361 ms |
492 KB |
Output is correct |
53 |
Correct |
381 ms |
492 KB |
Output is correct |
54 |
Correct |
359 ms |
492 KB |
Output is correct |
55 |
Correct |
407 ms |
492 KB |
Output is correct |
56 |
Correct |
345 ms |
396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
24 ms |
364 KB |
Output is correct |
10 |
Correct |
7 ms |
364 KB |
Output is correct |
11 |
Correct |
15 ms |
364 KB |
Output is correct |
12 |
Correct |
17 ms |
364 KB |
Output is correct |
13 |
Correct |
21 ms |
364 KB |
Output is correct |
14 |
Correct |
14 ms |
364 KB |
Output is correct |
15 |
Correct |
3 ms |
364 KB |
Output is correct |
16 |
Correct |
13 ms |
364 KB |
Output is correct |
17 |
Correct |
35 ms |
364 KB |
Output is correct |
18 |
Correct |
19 ms |
364 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 |
1 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 |
11 ms |
364 KB |
Output is correct |
35 |
Correct |
32 ms |
384 KB |
Output is correct |
36 |
Correct |
40 ms |
364 KB |
Output is correct |
37 |
Correct |
92 ms |
392 KB |
Output is correct |
38 |
Correct |
105 ms |
492 KB |
Output is correct |
39 |
Correct |
31 ms |
364 KB |
Output is correct |
40 |
Correct |
1 ms |
364 KB |
Output is correct |
41 |
Correct |
21 ms |
364 KB |
Output is correct |
42 |
Correct |
34 ms |
364 KB |
Output is correct |
43 |
Correct |
6 ms |
364 KB |
Output is correct |
44 |
Correct |
22 ms |
364 KB |
Output is correct |
45 |
Correct |
30 ms |
364 KB |
Output is correct |
46 |
Correct |
36 ms |
492 KB |
Output is correct |
47 |
Correct |
11 ms |
364 KB |
Output is correct |
48 |
Correct |
2 ms |
364 KB |
Output is correct |
49 |
Correct |
84 ms |
364 KB |
Output is correct |
50 |
Correct |
42 ms |
492 KB |
Output is correct |
51 |
Correct |
57 ms |
364 KB |
Output is correct |
52 |
Correct |
41 ms |
364 KB |
Output is correct |
53 |
Correct |
37 ms |
364 KB |
Output is correct |
54 |
Correct |
94 ms |
364 KB |
Output is correct |
55 |
Correct |
32 ms |
364 KB |
Output is correct |
56 |
Correct |
48 ms |
492 KB |
Output is correct |
57 |
Correct |
44 ms |
364 KB |
Output is correct |
58 |
Correct |
364 ms |
364 KB |
Output is correct |
59 |
Correct |
393 ms |
492 KB |
Output is correct |
60 |
Correct |
361 ms |
492 KB |
Output is correct |
61 |
Correct |
381 ms |
492 KB |
Output is correct |
62 |
Correct |
359 ms |
492 KB |
Output is correct |
63 |
Correct |
407 ms |
492 KB |
Output is correct |
64 |
Correct |
345 ms |
396 KB |
Output is correct |
65 |
Correct |
0 ms |
364 KB |
Output is correct |
66 |
Correct |
0 ms |
364 KB |
Output is correct |
67 |
Incorrect |
393 ms |
364 KB |
Output isn't correct |
68 |
Halted |
0 ms |
0 KB |
- |