Submission #48840

#	Time	Username	Problem	Language	Result	Execution time	Memory
48840		mrtsima22	Chessboard (IZhO18_chessboard)	C++17	39 / 100	62 ms	2260 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 ans=lmx,ansT;
int a[100003],b[100003],c[100003],d[100004];
int main(){std::ios::sync_with_stdio(false);
cin>>n>>k;
ansT=0LL;
for(long long i=0;i<k;i++)
{
	cin>>a[i]>>b[i]>>c[i]>>d[i];
a[i]--,b[i]--,c[i]--,d[i]--;	
}
ans=lmax;
  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: 0 / 8
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 0 / 23
• Subtask 6: 0 / 30