結果
問題 | 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);elsereturn (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;}