Submission #48843

#	Time	Username	Problem	Language	Result	Execution time	Memory
48843		mrtsima22	Chessboard (IZhO18_chessboard)	C++17	70 / 100	161 ms	2196 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;
#define lo long
const int lmax=1999999999;
const long long lmx=1999999999999999999;
  int n, k;
  long long ansT, ans = 10000000000LL;
  int a[100000], b[100000], x2[100000], y2[100000];
int main(){std::ios::sync_with_stdio(false);
cin>>n>>k;
for(long long i=0;i<k;i++)
{
	cin>>a[i]>>b[i]>>x2[i]>>y2[i];
a[i]--,b[i]--,y2[i]--,x2[i]--;	
}
  for(int j = 1; j < n; ++j)
    if(n % j == 0) { 
      ansT = 0;
      for(int i = 0; i < k; ++i)
        if((a[i]/j + b[i]/j) % 2 == 0)
          ++ansT;
      ansT = ansT * 2 - k;
      if(ansT + (long long)n * n / j / j / 2 * j * j < ans)
        ans = ansT + (long long)n * n / j / j / 2 * j * j;
      ansT = -ansT;
      if(ansT + ((long long)n * n / j / j + 1) / 2 * j * j < ans)
        ans = ansT + ((long long)n * n / j / j + 1) / 2 * j * j;
    }
//cout<<ansT+K-ansS<<" "<<ansS+k-ansT<<endl;

cout<<ans<<endl;
}
/*

                   *         *
                  * *       * *
                 *   *     *   *
                *     *   *     *
               *       * *       *
               *        *        *
                *               *
                 *             *
                  *           *
                   *         *
                    *       *
                     *     *
                      *   *
                       * *
                        *



*/

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