제출 #241518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
241518		mhy908	Chessboard (IZhO18_chessboard)	C++14	8 / 100	37 ms	1280 KiB

chessboard

#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(x.begin(), x.end())
#define press(x) x.erase(unique(x.begin(), x.end()), x.end())
#define lb(x, v) lower_bound(x.begin(), x.end(), v)
#define ub(x, v) upper_bound(x.begin(), x.end(), v)
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=2000000000000000000;
const LL mod1=1000000007;
const LL mod2=998244353;
const int inf=2000000000;
int n, k;
pair<pii, pii> rect[100010];
LL ans=llinf;
LL query2(int x, int y, int s){
    LL ret=0;
    int tx=x/s, ty=y/s;
    ret+=(LL)tx*ty/2*s*s;
    int rx=x%s, ry=y%s;
    if(tx%2)ret+=(LL)rx*(ty+1)/2*s;
    else ret+=(LL)rx*ty/2*s;
    if(ty%2)ret+=(LL)ry*(tx+1)/2*s;
    else ret+=(LL)ry*tx/2*s;
    if((tx+ty)%2)ret+=(LL)rx*ry;
    return ret;
}
pll query(int stx, int sty, int finx, int finy, int s){
    LL w=query2(finx, finy, s)-query2(stx-1, finy, s)-query2(finx, sty-1, s)+query2(stx-1, sty-1, s);
    LL b=(LL)(finx-stx+1)*(finy-sty+1)-w;
    return mp(b, w);
}
int main(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<=k; i++){
        scanf("%d %d %d %d", &rect[i].F.F, &rect[i].F.S, &rect[i].S.F, &rect[i].S.S);
    }
    for(int i=1; i<n; i++){
        if(n%i)continue;
        LL w1=0, b1=0;
        for(int j=1; j<=k; j++){
            pll tmp=query(rect[j].F.F, rect[j].F.S, rect[j].S.F, rect[j].S.S, i);
            w1+=tmp.F;
            b1+=tmp.S;
        }
        LL temp1=w1+(LL)(n/i)*(n/i)/2*i*i-b1;
        LL temp2=b1+(LL)(n/i)*(n/i)/2*i*i-w1;
        ans=min(ans, min(temp1, temp2));
    }
    printf("%lld", ans);
}
/*
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
*/

컴파일 시 표준 에러 (stderr) 메시지

chessboard.cpp: In function 'int main()':
chessboard.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~
chessboard.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d", &rect[i].F.F, &rect[i].F.S, &rect[i].S.F, &rect[i].S.S);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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