Submission #90102

#	Time	Username	Problem	Language	Result	Execution time	Memory
90102		Abelyan	Chessboard (IZhO18_chessboard)	C++17	100 / 100	473 ms	68544 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=100005;
int l1[N],l2[N],r1[N],r2[N];
ll prsp[N],prsv[N];
int main(){
    ll n;
    int k;
    cin>>n>>k;
    for (int i=0;i<k;i++){
        cin>>l1[i]>>l2[i]>>r1[i]>>r2[i];
    }
    ll mn=LLONG_MAX;
    for (ll i=1;i<n;i++){
        if (n%i)continue;
        ll qan;
        if ((n/i)%2) qan=(n*n-i*i)/2ll;
        else qan=(n*n)/2;
        prsp[0]=prsv[0]=0;
        //cout<<i<<" "<<qan<<endl;
        for (ll j=1;j<=n;j++){
            prsp[j]=prsp[j-1];
            prsv[j]=prsv[j-1];
            if (((j-1ll)/i)%2){
                prsv[j]++;
            }
            else{
                prsp[j]++;
            }
            //cout<<prsv[j]<<" "<<prsp[j]<<endl;
        }
        for (int j=0;j<k;j++){
            ll vqansp,vqansv,kqansp,kqansv;
            vqansp=prsp[r1[j]]-prsp[l1[j]-1];
            vqansv=prsv[r1[j]]-prsv[l1[j]-1];
            kqansp=prsp[r2[j]]-prsp[l2[j]-1];
            kqansv=prsv[r2[j]]-prsv[l2[j]-1];
            //cout<<vqansp<<" "<<vqansv<<" "<<kqansp<<" "<<kqansv<<endl;
            qan+=(vqansp*kqansp+vqansv*kqansv)-(vqansp*kqansv+vqansv*kqansp);
        }
        //cout<<qan<<endl;
        mn=min(mn,min(qan,n*n-qan));
    }
    cout<<mn<<endl;
    return 0;
}

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