Submission #93163

#	Time	Username	Problem	Language	Result	Execution time	Memory
93163		Makhsud	Chessboard (IZhO18_chessboard)	C++17	39 / 100	140 ms	508 KiB

chessboard

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll n, k, cnt, x, y, xx, yy;
ll a[50005][3][3];
vector <ll> d;

int main()
{
	cin >> n >> k;
	for ( int i = 1; i < n; i ++ ) {
		if ( n % i == 0 ) {
			d.push_back(i);
		}
	}
	for ( int i = 1; i <= k; i ++ ) {
		cin >> x >> y >> xx >> yy;
		ll r, c;
		for ( auto e: d ) {
			r = (x/e) + ( (x%e) && 1 );
			c = (y/e) + ( (y%e) && 1 );
			a[e][r%2][c%2] ++;
		}
	}
	ll ans1, ans2, mn = INT_MAX;
	for ( auto e: d ) {
		ans1 = ans2 = 0;
		for ( int i = 1; i <= (n/e); i ++ ) {
			if ( i % 2 == 1 ) {
				ans1 += (e*e) * ( (n/e) / 2 );
				ans2 += (e*e) * ( ( (n/e) + 1 ) / 2 );
			} else {
				ans1 += (e*e) * ( ( (n/e) + 1 ) / 2 );
				ans2 += (e*e) * ( (n/e) / 2 );
			}
		}		
		ans1 = ans1 + a[e][1][1] + a[e][0][0];
		ans2 = ans2 + a[e][1][0] + a[e][0][1];
		ans1 = ans1 - ( a[e][1][0] + a[e][0][1] );
		ans2 = ans2 - ( a[e][1][1] + a[e][0][0] );
		mn = min ( mn, min ( ans1, ans2 ) );
	}
	cout << mn;
}

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