Submission #1108499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108499		Muhammet	Chessboard (IZhO18_chessboard)	C++17	100 / 100	106 ms	5112 KiB

chessboard

#include <bits/stdc++.h>

using namespace std;

#define ll long long

vector <ll> p;

ll f(ll x1, ll y1, ll x2, ll y2){
	ll z = (p[y2] - p[y1-1]);
	z *= (p[x2] - p[x1-1]);
	z += (((x2-x1+1) - (p[x2] - p[x1-1])) * ((y2-y1+1) - (p[y2] - p[y1-1])));
	return z;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);

	ll n, k, k1 = 0;
	cin >> n >> k;
	vector <int> x1(k+1), y1(k+1), x2(k+1), y2(k+1);
	for(int i = 1; i <= k; i++){
		cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
		ll a = (x2[i] - x1[i] + 1), b = (y2[i] - y1[i] + 1);
		a *= b;
		k1 += a;
	}
	ll ans = n, n1 = n;
	ans *= n;
	n1 *= n;
	// cout << k1 << "\n";
	for(ll x3 = 1; x3 < n; x3++){
		if(n % x3 != 0) continue;
		p.assign(n+2,0);
		ll x = (x3 * 2), cnt = 0;
		for(int i = 1; i <= n; i++){
			p[i] = p[i-1] + ((i % x) <= (x / 2) and (i % x) != 0);
		}
		for(int i = 1; i <= k; i++){
			cnt += f(x1[i], y1[i], x2[i], y2[i]);
		}
		// cout << x3 << ' ' << cnt << "\n";
		ll y = ((x3 * x3) * (((n / x3) + 1) / 2) * (((n / x3) + 1) / 2)) + ((x3 * x3) * ((n / x3) / 2) * ((n / x3) / 2));
		ans = min(ans, (y - cnt + (k1-cnt)));
		ans = min(ans, (n1 - y) - (k1-cnt) + cnt);
	}
	cout << ans;
}

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