Submission #879129

#	Time	Username	Problem	Language	Result	Execution time	Memory
879129		TahirAliyev	Chessboard (IZhO18_chessboard)	C++17	100 / 100	194 ms	6628 KiB

chessboard

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<ll, ll>
#define oo 1e12
#define int ll


int n, k;
const int MAX = 1e5 + 5;
vector<array<int, 4>> black;

vector<int> s;

signed main(){
    cin >> n >> k;
    for(int i = 1; i <= k; i++){
        int a, b, c, d; cin >> a >> b >> c >> d;
        black.push_back({a, b, c, d});
    }
    s.push_back(1);
    for(int d = 2; d * d <= n; d++){
        if(n % d == 0){
            s.push_back(d);
            if(n / d != d){
                s.push_back(n / d);
            }
        }
    }
    int ans = oo;
    for(int a : s){
        int pre[n + 1];
        pre[0] = 0;
        for(int i = 1; i <= n; i++){
            pre[i] = pre[i - 1] + (((i - 1) / a + 1) % 2);
        }
        int tmp = ((n / a) * (n / a) + 1) / 2 * a * a;
        for(auto b : black){
            int p1 = pre[b[2]] - pre[b[0] - 1];
            int p2 = pre[b[3]] - pre[b[1] - 1];
            int x = (b[2] - b[0] + 1);
            int y = (b[3] - b[1] + 1);
            tmp -= x * y - 2 * (p1 * (y - p2) + p2 * (x - p1));
        }
        ans = min(tmp, ans);    
        ans = min(n * n - tmp, ans);
    }
    cout << ans << '\n';
}

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