Submission #674818

#	Time	Username	Problem	Language	Result	Execution time	Memory
674818		LucaIlie	Chessboard (IZhO18_chessboard)	C++17	70 / 100	378 ms	4232 KiB

chessboard

#include <bits/stdc++.h>

using namespace std;

const int maxK = 1e5;

struct rectangle {
    int l1, c1, l2, c2;
};

rectangle black[maxK];

int main() {
    int n, k;
    long long cost, minCost;

    cin >> n >> k;
    for ( int i = 0; i < k; i++ )
        cin >> black[i].l1 >> black[i].c1 >> black[i].l2 >> black[i].c2;

    minCost = (long long)n * n;
    for ( int l = 1; l < n; l++ ) {
        if ( n % l == 0 ) {
            int x = (n / l + 1) / 2, y = n / l / 2;

            cost = ((long long)l * l) * ((long long)x * x + (long long)y * y);
            for ( int i = 0; i < k; i++ ) {
                int lin = (black[i].l1 - 1) / l;
                int col = (black[i].c1 - 1) / l;

                if ( (lin + col) % 2 == 0 )
                    cost--;
                else
                    cost++;
            }
            minCost = min( minCost, cost );

            cost = (long long)2 * x * y * l * l;
            for ( int i = 0; i < k; i++ ) {
                int lin = (black[i].l1 - 1) / l;
                int col = (black[i].c1 - 1) / l;

                if ( (lin + col) % 2 == 0 )
                    cost++;
                else
                    cost--;
            }
            minCost = min( minCost, cost );
        }
    }

    cout << minCost;

    return 0;
}

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