Submission #93415

#	Time	Username	Problem	Language	Result	Execution time	Memory
93415		mirbek01	Chessboard (IZhO18_chessboard)	C++11	100 / 100	1704 ms	4320 KiB

chessboard

# include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

int n, k, a[N], b[N], c[N], d[N];
long long ans = 1e18;

long long white(int n, int m, int x){
      int a = n / x, b = m / x;
      long long ret = ((a + 1) / 2) * 1ll * ((b + 1) / 2) * 1ll * x * x;
      ret += (a / 2) * 1ll * (b / 2) * 1ll * x * x;
      if(b % 2 == 0){
            ret += ((a + 1) / 2) * 1ll * x * (m - b * x);
      } else {
            ret += (a / 2) * 1ll * x * (m - b * x);
      }
      if(a % 2 == 0){
            ret += ((b + 1) / 2) * 1ll * x * (n - a * x);
      } else {
            ret += (b / 2) * 1ll * x * (n - a * x);
      }
      if((a + b) % 2 == 0)
            ret += (n - a * x) * 1ll * (m - b * x);
      return ret;
}

long long get(int x){
      long long ret, cc = n / x;
      ret = ((cc * cc) / 2) * x * 1ll * x;
      for(int i = 1; i <= k; i ++){
            long long wh = white(c[i], d[i], x) - white(a[i] - 1, d[i], x) - white(c[i], b[i] - 1, x) + white(a[i] - 1, b[i] - 1, x);
            ret -= (c[i] - a[i] + 1) * 1ll * (d[i] - b[i] + 1) - wh;
      }
      for(int i = 1; i <= k; i ++){
            long long wh = white(c[i], d[i], x) - white(a[i] - 1, d[i], x) - white(c[i], b[i] - 1, x) + white(a[i] - 1, b[i] - 1, x);
            ret += wh;
      }
      return min(ret, n * 1ll * n - ret);
}

int main(){
      scanf("%d %d", &n, &k);

      for(int i = 1; i <= k; i ++){
            scanf("%d %d %d %d", a + i, b + i, c + i, d + i);
      }

      for(int i = 1; i * i <= n; i ++){
            if(n % i == 0){
                  ans = min(ans, get(i));
                  if(i != 1) ans = min(ans, get(n / i));
            }
      }

      cout << ans << endl;
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:44:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &n, &k);
       ~~~~~^~~~~~~~~~~~~~~~~
chessboard.cpp:47:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d %d %d", a + i, b + i, c + i, d + i);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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