Submission #1107898

#TimeUsernameProblemLanguageResultExecution timeMemory
1107898KasymKChessboard (IZhO18_chessboard)C++17
0 / 100
978 ms3012 KiB
#include "bits/stdc++.h" using namespace std; #define ff first #define ss second #define all(v) v.begin(), v.end() #define ll long long #define pb push_back #define pii pair<int, int> #define pli pair<ll, int> #define pll pair<ll, ll> #define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i) #define wr puts("----------------") template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;} template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;} using node = tuple<int, int, int, int>; const ll INF = 1e18; ll answer = INF; vector<node> adj; int n, kk; ll f(int x, int y, int xx){ ll sm = 0, _x = (x/xx)*1ll*xx, _y = (y/xx)*1ll*xx; if((_x/xx+_y/xx)&1){ sm += ((_x/xx)*1ll*(_y/xx))/2*1ll*(xx*1ll*xx); sm += (_y/xx+1)/2*1ll*(x-_x)*1ll*xx; sm += (_x/xx+1)/2*1ll*(y-_y)*1ll*xx; } else{ sm += ((_x/xx)*1ll*(_y /xx)+1)/2*1ll*(xx*1ll*xx); sm += (_y/xx)/2*1ll*(x-_x)*1ll*xx; sm += ((_x/xx))/2*1ll*(y-_y)*1ll*xx; sm += (x-_x)*1ll*(y-_y); } return sm; } void solve(int x){ ll ans = n*1ll*n-f(n, n, x); for(auto xx : adj){ int a, b, c, d; tie(a, b, c, d) = xx; ll w = f(c, d, x)+f(a-1, b-1, x)-f(c, b-1, x)-f(a-1, d, x); ans += w, ans -= (c-a+1)*1ll*(d-b+1)-w; } umin(answer, ans); umin(answer, n*1ll*n-ans); } int main(){ scanf("%d%d", &n, &kk); bool done = 1; for(int i = 1; i <= kk; ++i){ int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d); adj.pb({a, b, c, d}); done &= (a==c and b==d); } assert(done); for(int i = 1; i*i <= n; ++i){ solve(i); if(i!=n/i and i>1) solve(n/i); } printf("%lld\n", answer); return 0; }

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d%d", &n, &kk);
      |     ~~~~~^~~~~~~~~~~~~~~~~
chessboard.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         scanf("%d%d%d%d", &a, &b, &c, &d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...