oj.uz

Submission #93413

# Submission time Handle Problem Language Result Execution time Memory
93413 2019-01-08T10:26:00 Z mirbek01 Chessboard (IZhO18_chessboard) C++11
8 / 100
 30 ms 1272 KB 
# 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 *1ll* x) * x;
      } else {
            ret += (b / 2) * 1ll * (n - a *1ll* x) * x;
      }
      if(b % 2 == 0){
            ret += ((a + 1) / 2) * 1ll * (m - b *1ll* x) * x;
      } else {
            ret += (a / 2) * 1ll * (m - b *1ll* x) * x;
      }
      if(a % 2 == 0 && b % 2 == 0)
            ret += (n - a *1ll* x) * 1ll * (m - b *1ll* x);
      return ret;
}

long long get(int x){
      long long ret, cc = n / x;
      ret = ((cc * cc) / 2) * 1ll * x * x;
      for(int i = k; 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

chessboard.cpp: In function 'int main()':
chessboard.cpp:43: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:46: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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 252 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 252 KB Output is correct
8 Correct 2 ms 256 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 1272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 1272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 252 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 252 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Incorrect 30 ms 1272 KB Output isn't correct
10 Halted 0 ms 0 KB -