Submission #1312800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312800		arman.khachatryan	Chessboard (IZhO18_chessboard)	C++20	0 / 100	162 ms	327680 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;
const int INF=1e9+10;
int main() {
    int n, k;
    while(cin>>n>>k){
        int dp[n+2][n+2]={0}, x1, x2, y1, y2;
        while(k--){
            cin>>x1>>y1>>x2>>y2;
            for(int i=0; i<=x2-x1; i++){
                dp[x1+i][y1]++;
                dp[x1+i][y2+1]--;
            }
        }
        vector<int> v;
        for(int i=1; i<=sqrtl(n); i++){
            if(n%i==0){
                v.push_back(i);
                v.push_back(n/i);
            }
        }
        int ans=INF, last_ans, cur;
        for(auto& it: v){
            last_ans=0;
            for(int i=1; i<=n; i++){
                cur=0;
                for(int j=1; j<=n; j++){
                    cur+=dp[i][j];
                    int k=i/it, d=j/it;
                    if(k*it<i){
                        k++;
                    }
                    if(d*it<j){
                        d++;
                    }
                    k%=2;
                    d%=2;
                    if(k+d==1){
                        if(cur==1){
                            last_ans++;
                        }
                    }else if(cur==0){
                        last_ans++;
                    }
                }
            }
            ans=min(ans, min(last_ans, 2*n*n-last_ans));
            
        }
        cout<<ans<<'\n';
    }
}

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