Submission #1133152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133152		Muhammet	Chessboard (IZhO18_chessboard)	C++17	100 / 100	93 ms	2632 KiB

chessboard

#include "bits/stdc++.h"

using namespace std;

#define SZ(s) (int)s.size()
#define ff first
#define ss second
#define ll long long

const int N = 1e5+5;

ll T, n, k, a[N];

ll f(int x1, int y1, int x2, int y2){
	return (1LL * (a[y2]-a[y1-1]) * (a[x2]-a[x1-1])) + (1LL * ((y2-y1+1) - (a[y2]-a[y1-1])) * ((x2-x1+1) - (a[x2]-a[x1-1])));
}

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

	cin >> n >> k;
	vector <int> x1(k+1), y1(k+1), x2(k+1), y2(k+1);
	ll s = 0;
	for(int i = 1; i <= k; i++){
		cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
		s += (1LL * (x2[i]-x1[i]+1) * (y2[i]-y1[i]+1));
	}
	ll ans = 1e15;
	for(int x = 1; x < n; x++){
		if(n % x != 0) continue;
		for(int i = 0; i < n; i++){
			a[i+1] = ((i/x) % 2);
			a[i+1] += a[i];
		}
		ll sm = (a[n]*a[n]) + ((n-a[n]) * (n-a[n]));
		// cout << x << ' ' << sm << '\n';
		ll m = 0, m1 = 0, sm1 = s, sm2 = s;
		for(int i = 1; i <= k; i++){
			ll f1 = f(x1[i], y1[i], x2[i], y2[i]);
			sm1 -= f1;
			sm2 -= ((1LL * (x2[i]-x1[i]+1) * (y2[i]-y1[i]+1)) - f1); 
			m += f1;
			m1 += ((1LL * (x2[i]-x1[i]+1) * (y2[i]-y1[i]+1)) - f1);
		}
		m1 += (sm-sm2);
		m += (((n*n)-sm)-sm1);
		// cout << x << ' ' << m << ' ' << m1 << '\n';
		ans = min(min(m,m1), ans);
	}
	cout << ans << "\n";

	return 0;
}

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