Submission #342214

#TimeUsernameProblemLanguageResultExecution timeMemory
342214ogibogi2004Chessboard (IZhO18_chessboard)C++14
100 / 100
792 ms4460 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long const ll MAXN=1e5+6; const ll INF=2e17; ll emi_da(ll x,ll k) { ll t=(x-1)/k; t/=2; ll f=t*(2*k)+1; return t*k+min(k,(x-f+1)); } struct rect { ll x1,y1,x2,y2; }r[MAXN]; ll calc_black(rect r1,int k) { ll t1=emi_da(r1.x1-1,k),t2=emi_da(r1.x2,k); ll t=t2-t1; ll h1=emi_da(r1.y1-1,k),h2=emi_da(r1.y2,k); ll h=h2-h1; return t*h+(r1.x2-r1.x1+1-t)*(r1.y2-r1.y1+1-h); } ll ans=INF; int main() { ll n,k; cin>>n>>k; for(ll i=1;i<=k;i++)cin>>r[i].x1>>r[i].y1>>r[i].x2>>r[i].y2; for(ll i=1;i<=n/2;i++) { //cout<<i<<":\n"; if(n%i==0) { ll s=((n/i)*(n/i)+1)/2*(i*i); for(int j=1;j<=k;j++) { ll p=calc_black(r[j],i); //cout<<j<<" "<<p<<endl; s-=p; s+=(r[j].x2-r[j].x1+1)*(r[j].y2-r[j].y1+1)-p; } //cout<<s<<endl; ans=min(ans,s); s=((n/i)*(n/i))/2*(i*i); for(int j=1;j<=k;j++) { ll p=calc_black(r[j],i); s-=(r[j].x2-r[j].x1+1)*(r[j].y2-r[j].y1+1)-p; s+=p; } ans=min(ans,s); //cout<<s<<endl; } } cout<<ans<<endl; return 0; } /* 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 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...