제출 #1128802

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1128802		Gray	Chessboard (IZhO18_chessboard)	C++20	70 / 100	227 ms	3400 KiB

chessboard

#include <algorithm>
#include <bits/stdc++.h>
#include <cassert>
#include <iomanip>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair

const ll INF = 2e18;
const ll MOD = 1e9+7;

struct rect{
    ll si, sj, ti, tj;
    ll area(){
        return (ti-si+1)*(tj-sj+1);
    }
};


ll gencost(ll x, ll n, ll k, vector<rect> &a){
    ll asum=0, isum=0;
    for (auto rec:a){
        asum+=rec.area();
        // ll psi = (rec.si/x+(rec.si%x?1:0))*x;
        // ll psj = (rec.sj/x+(rec.sj%x?1:0))*x;
        // ll pti = (rec.ti/x)*x;
        // ll ptj = (rec.tj/x)*x;
        if ((rec.si/x+rec.sj/x)%2) isum++;
    }
    ll bsum = ((n/x)/2)*n*x+((n/x)%2?((n/x/2+1)*x*x):0);
    return min(bsum+isum-(asum-isum), (n*n-bsum)+(asum-isum)-isum);
}

void solve(){
    ll n, k; cin >> n >> k;
    vector<rect> a(k);
    for (ll i=0; i<k; i++){
        cin >> a[i].si >> a[i].sj >> a[i].ti >> a[i].tj;
        a[i].si--; a[i].sj--; a[i].ti--; a[i].tj--;
    }
    ll cost=INF;
    for (ll i=1; i*i<=n; i++){
        if (n%i==0){
            cost=min(cost, gencost(i, n, k, a));
            if(n/i!=n) cost=min(cost, gencost(n/i, n, k, a));
        }
    }
    cout << cost << ln;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    auto start = chrono::high_resolution_clock::now();
    ll t=1;
    // cin >> t;
    while (t--) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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