結果
問題 | No.325 マンハッタン距離2 |
ユーザー |
![]() |
提出日時 | 2024-07-28 18:27:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 1,764 bytes |
コンパイル時間 | 1,820 ms |
コンパイル使用メモリ | 166,624 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-28 18:27:13 |
合計ジャッジ時間 | 3,472 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include<bits/stdc++.h> #define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y) #define lowbit(x) x&(-x) #define pi pair<ll,ll> #define pii pair<ll,pair<ll,ll>> #define iip pair<pair<ll,ll>,ll> #define ppii pair<pair<ll,ll>,pair<ll,ll>> #define fi first #define se second #define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x #define Full(a) memset(a,0,sizeof(a)) #define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout); using namespace std; typedef double db; typedef unsigned long long ull; typedef long long ll; bool Begin; inline ll read(){ ll x=0,f=1; char c=getchar(); while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9'){ x=(x<<1)+(x<<3)+(c^48); c=getchar(); } return x*f; } inline void write(ll x){ if(x<0){ putchar('-'); x=-x; } if(x>9) write(x/10); putchar(x%10+'0'); } bool End; ll X1,Y1,X2,Y2,D; ll get(ll X,ll Y,ll D){ if(X<Y) swap(X,Y); if(D>=X+Y) return (X+1)*(Y+1); if(D>=X) return (X+1)*(Y+1)-(X+Y-D)*(X+Y-D+1)/2; if(D>=Y) return Y*(Y+1)/2+(Y+1)*(D-Y+1); return (D+1)*(D+2)/2; } ll solve(ll X1,ll Y1,ll X2,ll Y2,ll D){ ll ans=0; if(X1>X2) swap(X1,X2); if(Y1>Y2) swap(Y1,Y2); if(X1<0&&X2>0) return solve(1,Y1,-X1,Y2,D)+solve(0,Y1,X2,Y2,D); if(Y1<0&&Y2>0) return solve(X1,1,X2,-Y1,D)+solve(X1,0,X2,Y2,D); if(X1<0) return solve(-X2,Y1,-X1,Y2,D); if(Y1<0) return solve(X1,-Y2,X2,-Y1,D); ans+=get(X2,Y2,D); if(X1) ans-=get(X1-1,Y2,D); if(Y1) ans-=get(X2,Y1-1,D); if(X1&&Y1) ans+=get(X1-1,Y1-1,D); return ans; } int main(){ // open("manhattan.in","manhattan.out"); X1=read(),Y1=read(),X2=read(),Y2=read(),D=read(); write(solve(X1,Y1,X2,Y2,D)); return 0; }