제출 #342739

#제출 시각아이디문제언어결과실행 시간메모리
342739apostoldaniel854Chessboard (IZhO18_chessboard)C++14
100 / 100
691 ms4452 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define pb push_back #define dbg(x) cerr << #x << " " << x << "\n" const int MAX_N = 1e5; struct Rectangle { int x1; int y1; int x2; int y2; }; int get_line (int n, int l) { return n / (2 * l) * l + min (n % (2 * l), l); } ll calc (int n, int m, int l) { int onX = get_line (n, l); int onY = get_line (m, l); return 1ll * onX * onY + 1ll * (n - onX) * (m - onY); } ll solve (int n, int l, vector <Rectangle> &rect) { ll black_answer = calc (n, n, l), white_answer = 1ll * n * n - black_answer; for (Rectangle r : rect) { int black = calc (r.x2, r.y2, l) - calc (r.x1 - 1, r.y2, l) - calc (r.x2, r.y1 - 1, l) + calc (r.x1 - 1, r.y1 - 1, l); int white = 1ll * (r.x2 - r.x1 + 1) * (r.y2 - r.y1 + 1) - black; black_answer -= black; black_answer += white; white_answer -= white; white_answer += black; } return min (white_answer, black_answer); } int main () { ios::sync_with_stdio (false); cin.tie (0); cout.tie (0); int n, k; cin >> n >> k; vector <Rectangle> rect; for (int i = 1; i <= k; i++) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; rect.pb ({x1, y1, x2, y2}); } ll ans = 1ll * n * n; for (int length = 1; length < n; length++) if (n % length == 0) ans = min (ans, solve (n, length, rect)); cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...