Submission #76766

# Submission time Handle Problem Language Result Execution time Memory
76766 2018-09-17T15:31:06 Z zetapi Chessboard (IZhO18_chessboard) C++14
8 / 100
23 ms 2376 KB
#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 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((arr[A].first+arr[A].second)%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%2))*X*X;
	for(int A=1;A<=K;A++)
	{
		if((arr[A].first+arr[A].second)%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;
	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;
}
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 516 KB Output is correct
6 Correct 2 ms 520 KB Output is correct
7 Correct 2 ms 580 KB Output is correct
8 Correct 2 ms 584 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 2376 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2376 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2376 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 2376 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 516 KB Output is correct
6 Correct 2 ms 520 KB Output is correct
7 Correct 2 ms 580 KB Output is correct
8 Correct 2 ms 584 KB Output is correct
9 Incorrect 23 ms 2376 KB Output isn't correct
10 Halted 0 ms 0 KB -