結果
問題 | 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# functionsdef f(x, y, d): # [0, x) * [0, y)assert 0 <= xassert 0 <= yif x == 0 or y == 0:return 0x -= 1y -= 1d = min(d, x + y)ans = (d+1)*(d+2)//2if x <= d:dx = d-xans -= dx*(dx+1)//2if y <= d:dy = d-yans -= dy*(dy+1)//2ans -= min(x,d)+1ans -= min(y,d)+1ans += 1return ansdef g(x1, x2, y1, y2, d):if x1 <= 0 <= x2:if 0 <= y1 <= y2:if y1 <= d:ans = min(d, y2) - min(d, y1) + 1if y1 == 0:ans -= 1return anselse:return 0elif y1 <= 0 <= y2:return min(d, abs(y1)) + min(d, y2)assert Falseelse:return 0def h(x1, x2, y1, y2, d):if x1 <= 0 <= x2 and y1 <= 0 <= y2:return 1else:return 0# inputx1, y1, x2, y2, d = map(int,input().split())assert x1 < x2assert y1 < y2if x2 <= 0:x1, x2 = - x2, - x1if y2 <= 0:y1, y2 = - y2, - y1if x1 <= 0:x1, y1 = y1, x1x2, y2 = y2, x2# calcans = 0if x1 <= 0:assert x1 <= 0 <= x2assert y1 <= 0 <= y2ans += 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 < x2assert y1 <= 0 <= y2ans -= 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 < x2assert 0 <= y1 < y2ans += 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)# outputprint(ans)