Submission #341348

#	Time	Username	Problem	Language	Result	Execution time	Memory
341348		Tosic	Chessboard (IZhO18_chessboard)	C++14	39 / 100	94 ms	1536 KiB

chessboard

#include <bits/stdc++.h>

using namespace std;

int n, k;
long long ans;
vector<pair<int, int> > allW;

void tryFor(int d){
	if(d == n){
		return;
	}
	// 0 0 is black
	long long blArea = 1LL*d*d*(((n/d)*(n/d)+1)/2);
	for(auto i : allW){
		if( (i.first/d + i.second/d)%2 ){
			blArea++;
		} else {
			blArea--;
		}
	}
	ans = min(ans, blArea);
	// 0 0 is BUANA
	blArea = 1ll*d*d*(((n/d)*(n/d))/2);
	for(auto i : allW){
		//cerr << i.first/d + i.second/d << '\n';
		if( (i.first/d + i.second/d)%2 ){
			blArea--;
		} else {
			blArea++;
		}
	}
	ans = min(ans, blArea);
	return;
}

int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin >> n >> k;
	ans = 1e10;
	for(int i = 0; i < k; ++i){
		int x, y;
		cin >> x >> y;
		cin >> x >> y;
		--x,--y;
		allW.push_back({x,y});
	}
	for(int i = 1; i*i <= n; ++i){
		if(n%i == 0){
			tryFor(n/i);
			tryFor(i);
		}
	}
	cout<<ans;
}

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