結果
問題 | No.325 マンハッタン距離2 |
ユーザー |
![]() |
提出日時 | 2020-09-23 00:27:20 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 33 ms / 1,000 ms |
コード長 | 906 bytes |
コンパイル時間 | 195 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 10,752 KB |
最終ジャッジ日時 | 2024-06-27 01:06:21 |
合計ジャッジ時間 | 1,972 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
import sysread=sys.stdin.buffer.readreadline=sys.stdin.buffer.readlinereadlines=sys.stdin.buffer.readlinesx1, y1, x2, y2, d=map(int, readline().split())def solve0(x, y):if x>y:x, y=y, xif d<=x:return d*(d-1)//2elif d<=y:return d*(d-1)//2-(d-x)*(d-x-1)//2elif d<=x+y:return x*y-(x+y-d)*(x+y-d+1)//2else:return x*ydef solve(xl, xr, yl, yr):if xl>xr or yl>yr:return 0return solve0(xr, yr)-solve0(xl-1, yr)-solve0(xr, yl-1)+solve0(xl-1, yl-1)ans=0ans+=solve(max(1, x1), x2, max(1, y1), y2)ans+=solve(max(1, -x2), -x1, max(1, y1), y2)ans+=solve(max(1, x1), x2, max(1, -y2), -y1)ans+=solve(max(1, -x2), -x1, max(1, -y2), -y1)if x1<=0 and 0<=x2:ans+=max(0, min(d, y2)-max(-d, y1)+1)if y1<=0 and 0<=y2:ans+=max(0, min(d, x2)-max(-d, x1)+1)if x1<=0 and y1<=0 and x2>=0 and y2>=0:ans-=1print(ans)