oj.uz

Submission #76767

# Submission time Handle Problem Language Result Execution time Memory
76767 2018-09-17T15:33:46 Z zetapi Chessboard (IZhO18_chessboard) C++14
16 / 100
 42 ms 5336 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>>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 3 ms 376 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 552 KB Output is correct
5 Correct 2 ms 552 KB Output is correct
6 Correct 2 ms 552 KB Output is correct
7 Correct 2 ms 552 KB Output is correct
8 Correct 2 ms 636 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2168 KB Output is correct
2 Correct 9 ms 2168 KB Output is correct
3 Correct 24 ms 3316 KB Output is correct
4 Correct 23 ms 4036 KB Output is correct
5 Correct 42 ms 4768 KB Output is correct
6 Correct 19 ms 4768 KB Output is correct
7 Correct 5 ms 4768 KB Output is correct
8 Correct 17 ms 4768 KB Output is correct
9 Correct 41 ms 5336 KB Output is correct
10 Correct 25 ms 5336 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5336 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 5336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2168 KB Output is correct
2 Correct 9 ms 2168 KB Output is correct
3 Correct 24 ms 3316 KB Output is correct
4 Correct 23 ms 4036 KB Output is correct
5 Correct 42 ms 4768 KB Output is correct
6 Correct 19 ms 4768 KB Output is correct
7 Correct 5 ms 4768 KB Output is correct
8 Correct 17 ms 4768 KB Output is correct
9 Correct 41 ms 5336 KB Output is correct
10 Correct 25 ms 5336 KB Output is correct
11 Incorrect 2 ms 5336 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 3 ms 376 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 552 KB Output is correct
5 Correct 2 ms 552 KB Output is correct
6 Correct 2 ms 552 KB Output is correct
7 Correct 2 ms 552 KB Output is correct
8 Correct 2 ms 636 KB Output is correct
9 Correct 35 ms 2168 KB Output is correct
10 Correct 9 ms 2168 KB Output is correct
11 Correct 24 ms 3316 KB Output is correct
12 Correct 23 ms 4036 KB Output is correct
13 Correct 42 ms 4768 KB Output is correct
14 Correct 19 ms 4768 KB Output is correct
15 Correct 5 ms 4768 KB Output is correct
16 Correct 17 ms 4768 KB Output is correct
17 Correct 41 ms 5336 KB Output is correct
18 Correct 25 ms 5336 KB Output is correct
19 Incorrect 2 ms 5336 KB Output isn't correct
20 Halted 0 ms 0 KB -