Submission #608834

#	Time	Username	Problem	Language	Result	Execution time	Memory
608834		pakhomovee	Chessboard (IZhO18_chessboard)	C++17	70 / 100	322 ms	5708 KiB

chessboard

#include <iostream>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
#include <set>
#include <numeric>
#include <queue>

using namespace std;

#define int long long

struct rect {
    int x1, y1, x2, y2;
    rect() {}
};

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<rect> r(k);
    int S = 0;
    for (int i = 0; i < k; ++i) {
        cin >> r[i].x1 >> r[i].y1 >> r[i].x2 >> r[i].y2;
        --r[i].x1; --r[i].y1; --r[i].x2; --r[i].y2;
        S += (r[i].x2 - r[i].x1 + 1) * (r[i].y2 - r[i].y1 + 1);
    }
    int ans = n * n;
    for (int len = 1; len < n; ++len) {
        if (n % len) continue;
        if (1) {
            int cntSide = n / len;
            int black = (cntSide * cntSide + 1) / 2 * len * len;
            int wrongWhite = 0;
            for (rect q : r) {
                int par = (q.x1 / len + q.y1 / len) % 2;
                if (par == 1) {
                    wrongWhite++;
                }
            }
            ans = min(ans, wrongWhite * 2 + black - S);
        }
        if (1) {
            int cntSide = n / len;
            int black = (cntSide * cntSide) / 2 * len * len;
            int wrongWhite = 0;
            for (rect q : r) {
                int par = (q.x1 / len + q.y1 / len) % 2;
                if (par == 0) {
                    wrongWhite++;
                }
            }
            ans = min(ans, wrongWhite * 2 + black - S);
        }
    }
    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
*/

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