結果
問題 | No.325 マンハッタン距離2 |
ユーザー |
![]() |
提出日時 | 2016-06-08 18:24:53 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 1,270 bytes |
コンパイル時間 | 629 ms |
コンパイル使用メモリ | 64,852 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-09 03:14:45 |
合計ジャッジ時間 | 1,892 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include <iostream> #include <vector> #include <map> #include <algorithm> using namespace std; #define REP(i,s,e) for (i = s; i <= e; i++) #define rep(i,n) REP (i,0,(int)(n)-1) #define RREP(i,s,e) for (i = s; i >= e; i--) #define rrep(i,n) RREP (i,(int)(n)-1,0) #define INF (int)1e8 #define MOD (int)(1e9+7) typedef long long ll; int d; ll sum(int x) { return (ll) x * (x + 1) / 2; } ll f(int x, int y) { if (x >= d && y >= d) return sum(d+1); else if (y >= d) return sum(d+1) - sum(d-x); else if (x >= d) return sum(d+1) - sum(d-y); else return (ll) (x+1) * (y+1) - ((x + y > d ) ? sum(x + y - d) : 0); } ll g(int x1, int y1, int x2, int y2) { if (x2 < 0) return g(-x2,y1,-x1,y2); if (y2 < 0) return g(x1,-y2,x2,-y1); if (x1 < 0) return g(0,y1,x2,y2) + g(0,y1,-x1,y2) - g(0,y1,0,y2); if (y1 < 0) return g(x1,0,x2,y2) + g(x1,0,x2,-y1) - g(x1,0,x2,0); ll ret = f(x2,y2); if (x1 > 0) ret -= f(x1-1,y2); if (y1 > 0) ret -= f(x2,y1-1); if (x1 > 0 && y1 > 0) ret += f(x1-1,y1-1); return ret; } int main(void) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2 >> d; cout << g(x1,y1,x2,y2) << endl; return 0; }