Submission #1117429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117429		Petrix	Chessboard (IZhO18_chessboard)	C++17	100 / 100	147 ms	4364 KiB

chessboard

#include <iostream>
using namespace std;

int v[100001][4];

#define int long long

int calc(int i,int lun) {
    return i/(2*lun)*lun+min(i%(2*lun),lun);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,k,a,d,l1,l2,c1,c2,lin,col,i,j,rasp;
    cin>>n>>k;
    for(i=1;i<=k;i++){
        for(j=0;j<4;j++){
            cin>>v[i][j];
        }
    }
    rasp=n*n;
    for(d=1;d<n;d++){
        if(n%d==0){
            a=2*calc(n,d)*(n-calc(n,d));
            for(j=1;j<=k;j++){
                l1=v[j][0];c1=v[j][1];
                l2=v[j][2];c2=v[j][3];
                lin=calc(l2,d)-calc(l1-1,d);col=calc(c2,d)-calc(c1-1,d);
                a+=2*(l2-l1+1-lin)*(c2-c1+1-col)+2*lin*col-(l2-l1+1)*(c2-c1+1);
            }
            rasp=min(rasp,min(n*n-a,a));
        }

    }cout<<rasp;

    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