Submission #490794

#	Time	Username	Problem	Language	Result	Execution time	Memory
490794		infertechno2	Chessboard (IZhO18_chessboard)	C++14	70 / 100	224 ms	7256 KiB

chessboard

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll Size=1e5+1;

class point2d{
public:
    ll x,y;
};

point2d top[Size],bot[Size];
pair<ll,ll> ans[Size];

void solve(){
    ll n,k;
    cin>>n>>k;
    for(ll i=0;i<=n;i++){
        ans[i].first=1e18;
        ans[i].second=1e18;
    }
    for(ll i=0;i<k;i++){
        cin>>top[i].y>>top[i].x>>bot[i].y>>bot[i].x;
        top[i].y--;
        top[i].x--;
        bot[i].y--;
        bot[i].x--;
    }
    for(ll i=n/2;i>=1;i--){
        if(n%i==0){
            if((n/i)%2==1){
                ans[i].first=((n/i/2)*(n/i/2+1)*i*i)*2;
                ans[i].second=ans[i].first+i*i;
            }else{
                ans[i].first=n*n/2;
                ans[i].second=n*n/2;
            }
        }
    }
    ll best_ans=1e18;
    for(ll i=1;i<=n/2;i++){
        if(ans[i].first!=1e18){
            for(ll j=0;j<k;j++){
                if(((top[j].x/i)+(top[j].y/i))%2==1){
                    ans[i].first--;
                    ans[i].second++;
                }else{
                    ans[i].first++;
                    ans[i].second--;
                }
            }
            best_ans=min(best_ans,min(ans[i].first,ans[i].second));
        }
    }
    cout<<best_ans<<endl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
    while(t--){
        solve();
    }
    return 0;
}

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