Submission #289652

#	Time	Username	Problem	Language	Result	Execution time	Memory
289652		Leonardo_Paes	Chessboard (IZhO18_chessboard)	C++17	70 / 100	452 ms	3576 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef long long ll;
typedef pair<int,int> pii;
int main(){
    ll n, k;
    cin >> n >> k;
    if(k == 0){
        ll ans = n*n/2;
        for(ll i=2; i<=n; i++) if(n%i == 0) ans = min(ans, (i*i/2)*(n/i)*(n/i));
        cout << ans << "\n";
        return 0;
    }
    vector<pii> rec(k);
    for(int i=0; i<k; i++) cin >> rec[i].f >> rec[i].s >> rec[i].f >> rec[i].s;
    vector<ll> div;
    for(ll i=1; i*i<=n; i++){
        if(n%i == 0){
            div.push_back(i);
            if(n/i != i) div.push_back(n/i);
        }
    }
    ll ans = n*n;
    for(auto len : div){
        if(len == n) continue;
        ll a = 0, b = 0;
        for(auto r : rec){
            int i = (r.f + len - 1)/len;
            int j = (r.s + len - 1)/len;
            if((i+j)%2 == 0) a++;
            else b++;
        }
        ll qtdp = ((n/len)*(n/len)+1)/2*len*len;
        ll qtdb = n*n - qtdp;
        ans = min(ans, qtdp - a + b);
        ans = min(ans, qtdb - b + a);
    }
    cout << ans << "\n";
    /*
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