Submission #378506

#	Time	Username	Problem	Language	Result	Execution time	Memory
378506		daniel920712	Chessboard (IZhO18_chessboard)	C++14	39 / 100	50 ms	9708 KiB

chessboard

#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;
int all[1005][1005]={0};
int sum[1005][1005]={0};
int main()
{
    int N,M,ans=2e9,t,a,b,c,d,i,j,k;
    scanf("%d %d",&N,&M);
    while(M--)
    {
        scanf("%d %d %d %d",&a,&b,&c,&d);
        for(i=a;i<=c;i++) for(j=b;j<=d;j++) all[i][j]=1;
    }
    for(i=1;i<=N;i++) for(j=1;j<=N;j++) sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+all[i][j];
    for(i=1;i<N;i++)
    {
        if(N%i==0)
        {
            t=0;
            for(j=1;j<=N/i;j++)
            {
                for(k=1;k<=N/i;k++)
                {
                    if((j+k)%2) t+=sum[i*j][i*k]-sum[i*j][i*(k-1)]-sum[i*(j-1)][i*k]+sum[i*(j-1)][i*(k-1)];
                    else t+=(i*i)-(sum[i*j][i*k]-sum[i*j][i*(k-1)]-sum[i*(j-1)][i*k]+sum[i*(j-1)][i*(k-1)]);
                }
            }
            ans=min(ans,t);
            t=0;
            for(j=1;j<=N/i;j++)
            {
                for(k=1;k<=N/i;k++)
                {
                    if((j+k)%2==0) t+=sum[i*j][i*k]-sum[i*j][i*(k-1)]-sum[i*(j-1)][i*k]+sum[i*(j-1)][i*(k-1)];
                    else t+=(i*i)-(sum[i*j][i*k]-sum[i*j][i*(k-1)]-sum[i*(j-1)][i*k]+sum[i*(j-1)][i*(k-1)]);
                }
            }
            ans=min(ans,t);

        }
    }
    printf("%d\n",ans);
    return 0;
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   11 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
chessboard.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   14 |         scanf("%d %d %d %d",&a,&b,&c,&d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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