Submission #878740

#	Time	Username	Problem	Language	Result	Execution time	Memory
878740		Elvin_Fritl	Chessboard (IZhO18_chessboard)	C++17	39 / 100	99 ms	3668 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;
 
#define io                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

 
typedef long long ll;
 
ll bp(ll n,ll m){
    if(m == 0){
        return 1;
    }
    if(m == 1){
        return n;
    }
    if(m%2==0){
        return bp(n*n,m/2);
    }
    return n*bp(n,m-1);
}

 
const int N =  2505, M = 33, inf = 1e9 + 99;
const ll inff = 1e12;
 
int main()
{
	io;
	
	int n, k; 
	cin >> n >> k;
	ll res = n * n;
	ll a[k][4];
	for(int i=0;i<k;i++) {
		cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
	}
	for(int m=1;m<n;m++) {
		if(!(n % m)) { 
			ll tmp = (m * (n / (2 * m)) + min(m, n % (2 * m))) * (n - (m * (n / (2 * m)) + min(m, n % (2 * m)))) + (1LL * m * (n / (2 * m)) + min(1LL * m, 1LL * n % (2 * m))) * (n - (m * (n / (2LL * m)) + min(m, n % (2 * m))));
			for(int i=0;i<k;i++) {
				ll u = a[i][2] - a[i][0] + 1;
				ll x = (m * (a[i][2] / (2 * m)) + min(1LL * m, 1LL * a[i][2] % (2 * m))) - (m * ((a[i][0] - 1) / (2 * m)) + min(1LL * m,1LL *  (a[i][0] - 1) % (2LL * m)));
				ll v = a[i][3] - a[i][1] + 1;
				ll y = (m * (a[i][3] / (2 * m)) + min(1LL * m, 1LL * a[i][3] % (2 * m))) - (1LL * m * ((a[i][1] - 1) / (2 * m)) + min(1LL * m, 1LL * (a[i][1] - 1) % (2LL * m)));;
				tmp += 2 * (x * y + (u - x) * (v - y)) - u * v;
			}
			res = min(res, min(tmp, n * n - tmp));
		}
	}
	cout << res << endl;
    
    return 0;
 
}

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