oj.uz

Submission #76768

# Submission time Handle Problem Language Result Execution time Memory
76768 2018-09-17T15:38:09 Z zetapi Chessboard (IZhO18_chessboard) C++14
16 / 100
 49 ms 2020 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 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%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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 448 KB Output is correct
4 Correct 2 ms 448 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 484 KB Output is correct
7 Correct 2 ms 540 KB Output is correct
8 Correct 2 ms 616 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1532 KB Output is correct
2 Correct 10 ms 1532 KB Output is correct
3 Correct 22 ms 1532 KB Output is correct
4 Correct 39 ms 1532 KB Output is correct
5 Correct 32 ms 1532 KB Output is correct
6 Correct 20 ms 1532 KB Output is correct
7 Correct 7 ms 1532 KB Output is correct
8 Correct 19 ms 1532 KB Output is correct
9 Correct 49 ms 2020 KB Output is correct
10 Correct 27 ms 2020 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1532 KB Output is correct
2 Correct 10 ms 1532 KB Output is correct
3 Correct 22 ms 1532 KB Output is correct
4 Correct 39 ms 1532 KB Output is correct
5 Correct 32 ms 1532 KB Output is correct
6 Correct 20 ms 1532 KB Output is correct
7 Correct 7 ms 1532 KB Output is correct
8 Correct 19 ms 1532 KB Output is correct
9 Correct 49 ms 2020 KB Output is correct
10 Correct 27 ms 2020 KB Output is correct
11 Incorrect 2 ms 2020 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 448 KB Output is correct
4 Correct 2 ms 448 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 484 KB Output is correct
7 Correct 2 ms 540 KB Output is correct
8 Correct 2 ms 616 KB Output is correct
9 Correct 34 ms 1532 KB Output is correct
10 Correct 10 ms 1532 KB Output is correct
11 Correct 22 ms 1532 KB Output is correct
12 Correct 39 ms 1532 KB Output is correct
13 Correct 32 ms 1532 KB Output is correct
14 Correct 20 ms 1532 KB Output is correct
15 Correct 7 ms 1532 KB Output is correct
16 Correct 19 ms 1532 KB Output is correct
17 Correct 49 ms 2020 KB Output is correct
18 Correct 27 ms 2020 KB Output is correct
19 Incorrect 2 ms 2020 KB Output isn't correct
20 Halted 0 ms 0 KB -