Submission #76769

#	Time	Username	Problem	Language	Result	Execution time	Memory
76769		zetapi	Chessboard (IZhO18_chessboard)	C++14	70 / 100	702 ms	2300 KiB

chessboard

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

#define pb  push_back
#define mp  make_pair
#define int long long
#define itr iterator

typedef pair<int,int> pii;

const int MAX=1e6;
const int INF=1e12;

pii arr[MAX];

int N,K,ans;

int cell(int a,int c)
{
	return (a-1)/c+1;
}

int cell(int a,int b,int c)
{
	a--;
	b--;
	a/=c;
	b/=c;
	a++;
	b++;
	return a+b;
}

int cal(int X)
{
	if(X==N)
		return INF;
	//At first color the cell (1,1) white
	int res=(((N/X)*(N/X))/2)*X*X;
	for(int A=1;A<=K;A++)
	{
		if(cell(arr[A].first,arr[A].second,X)%2==0)	//this cell should be white
			res++;
		else	//this cell should be black
			res--;
	}
	//Color the cell (1,1) black
	int res_2=(((N/X)*(N/X))/2+(N/X)%2)*X*X;
	for(int A=1;A<=K;A++)
	{
		if(cell(arr[A].first,arr[A].second,X)%2==0)	//this cell should be black
			res_2--;
		else
			res_2++;
	}
	return min(res,res_2);
}

signed main()
{
	ios_base::sync_with_stdio(false);

	ans=INF;
	cin>>N>>K;
	for(int A=1;A<=K;A++)
		cin>>arr[A].first>>arr[A].second>>arr[A].first>>arr[A].second;
	for(int A=1;A*A<=N;A++)
	{
		if(!(N%A))
		{
			if(A*A==N)
				ans=min(ans,cal(A));
			else
				ans=min(ans,cal(A)),
				ans=min(ans,cal(N/A));
		}
	}
	cout<<ans;
	return 0;
}

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