Submission #878825

#	Time	Username	Problem	Language	Result	Execution time	Memory
878825		TahirAliyev	Chessboard (IZhO18_chessboard)	C++17	39 / 100	91 ms	3016 KiB

chessboard

#include <bits/stdc++.h>

using namespace std;

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


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

vector<int> s;

void solve(){
    cin >> n >> k;
    for(int i = 1; i <= k; i++){
        int a, b; cin >> a >> b >> a >> b;
        black.push_back({a, b});
    }
    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 tmp1 = ((n / a) * (n / a) + 1) / 2 * a * a;
        int tmp2 = ((n / a) * (n / a)) / 2 * a * a;
        for(pii b : black){
            int x = (b.first - 1) / a + 1;
            int y = (b.second - 1) / a + 1;
            if(x % 2 == y % 2){
                tmp1--;
                tmp2++;
            }
            else{
                tmp1++;
                tmp2--;
            }
        }
        ans = min(tmp1, ans);
        ans = min(tmp2, ans);
    }
    cout << ans << '\n';
}

signed main(){
    int t = 1;
    while(t--){
        solve();
    }
}

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