結果
問題 | No.325 マンハッタン距離2 |
ユーザー |
|
提出日時 | 2016-06-28 22:40:16 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 33 ms / 1,000 ms |
コード長 | 1,822 bytes |
コンパイル時間 | 325 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 11,136 KB |
最終ジャッジ日時 | 2024-10-11 22:01:07 |
合計ジャッジ時間 | 2,093 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#!/usr/bin/env python3 # functions def f(x, y, d): # [0, x) * [0, y) assert 0 <= x assert 0 <= y if x == 0 or y == 0: return 0 x -= 1 y -= 1 d = min(d, x + y) ans = (d+1)*(d+2)//2 if x <= d: dx = d-x ans -= dx*(dx+1)//2 if y <= d: dy = d-y ans -= dy*(dy+1)//2 ans -= min(x,d)+1 ans -= min(y,d)+1 ans += 1 return ans def g(x1, x2, y1, y2, d): if x1 <= 0 <= x2: if 0 <= y1 <= y2: if y1 <= d: ans = min(d, y2) - min(d, y1) + 1 if y1 == 0: ans -= 1 return ans else: return 0 elif y1 <= 0 <= y2: return min(d, abs(y1)) + min(d, y2) assert False else: return 0 def h(x1, x2, y1, y2, d): if x1 <= 0 <= x2 and y1 <= 0 <= y2: return 1 else: return 0 # input x1, y1, x2, y2, d = map(int,input().split()) assert x1 < x2 assert y1 < y2 if x2 <= 0: x1, x2 = - x2, - x1 if y2 <= 0: y1, y2 = - y2, - y1 if x1 <= 0: x1, y1 = y1, x1 x2, y2 = y2, x2 # calc ans = 0 if x1 <= 0: assert x1 <= 0 <= x2 assert y1 <= 0 <= y2 ans += f(abs(x1)+1, abs(y1)+1, d) ans += f(abs(x1)+1, abs(y2)+1, d) ans += f(abs(x2)+1, abs(y1)+1, d) ans += f(abs(x2)+1, abs(y2)+1, d) elif y1 <= 0: assert 0 <= x1 < x2 assert y1 <= 0 <= y2 ans -= f(x1, abs(y1)+1, d) ans += f(x2+1, abs(y1)+1, d) ans -= f(x1, abs(y2)+1, d) ans += f(x2+1, abs(y2)+1, d) else: assert 0 <= x1 < x2 assert 0 <= y1 < y2 ans += f(x1, y1, d) ans -= f(x1, y2+1, d) ans -= f(x2+1, y1, d) ans += f(x2+1, y2+1, d) ans += g(x1, x2, y1, y2, d) ans += g(y1, y2, x1, x2, d) ans += h(x1, x2, y1, y2, d) # output print(ans)