Submission #93409

#	Time	Username	Problem	Language	Result	Execution time	Memory
93409		mirbek01	Chessboard (IZhO18_chessboard)	C++11	16 / 100	56 ms	3704 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 * 1ll * b + 1) / 2) * 1ll * x * x;
      if(a % 2 == 0){
            ret += ((b + 1) / 2) * 1ll * (n - a * x) * x;
      } else {
            ret += (b / 2) * 1ll * (n - a * x) * x;
      }
      if(b % 2 == 0){
            ret += ((a + 1) / 2) * 1ll * (m - b * x) * x;
      } else {
            ret += (a / 2) * 1ll * (m - b * x) * x;
      }
      if(a % 2 && b % 2)
            ret += (n - a * x) * (m - b * x);
      return ret;
}
long long black(int n, int m, int x){
      int a = n / x, b = m / x;
      long long ret = ((a * 1ll * b) / 2) * 1ll * x * x;
      if(a % 2 ){
            ret += ((b + 1) / 2) * 1ll * (n - a * x) * x;
      } else {
            ret += (b / 2) * 1ll * (n - a * x) * x;
      }
      if(b % 2){
            ret += ((a + 1) / 2) * 1ll * (m - b * x) * x;
      } else {
            ret += (a / 2) * 1ll * (m - b * x) * x;
      }
      if(a % 2 == 0 && b % 2 == 0)
            ret += (n - a * x) * (m - b * x);
      return ret;
}

long long get(int x){
      long long ret1, ret2, cc = n / x;
      ret1 = ((cc * cc) / 2) * 1ll * x * x;
      ret2 = ((cc * cc + 1) / 2) * 1ll * x * 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);
            long long bl = black(c[i], d[i], x) - black(a[i] - 1, d[i], x) - black(c[i], b[i] - 1, x) + black(a[i] - 1, b[i] - 1, x);
            ret1 -= (c[i] - a[i] + 1) * 1ll * (d[i] - b[i] + 1) - wh;
            ret2 -= (c[i] - a[i] + 1) * 1ll * (d[i] - b[i] + 1) - bl;
      }
      for(int i = 1; i <= k; i ++){
            ret1 += 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);
            ret2 += black(c[i], d[i], x) - black(a[i] - 1, d[i], x) - black(c[i], b[i] - 1, x) + black(a[i] - 1, b[i] - 1, x);
      }
      return min(ret1, ret2);
}

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;
}
/***
6 8
3 3 3 3
1 2 1 2
3 4 3 4
5 5 5 5
4 3 4 3
4 4 4 4
2 1 2 1
3 6 3 6
***/

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:63: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:66: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: 0 / 15
• Subtask 4: 0 / 16
• Subtask 5: 0 / 23
• Subtask 6: 0 / 30