TopCoder SRM 573 Div2 Hard: WolfPackDivTwo

コード

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <fstream>
#include <iostream>
#include <set>
#include <sstream>
#include <typeinfo>
#include <vector>

using namespace std;
typedef long long ll;

class WolfPackDivTwo {
  int dist(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
  }
  const int MOD = 1000000007;

 public:
  int calc(vector<int> x, vector<int> y, int m) {
    int N = x.size();
    const int S = 300, P = 100;
    vector<vector<ll>> dp(vector<vector<ll>>(S, vector<ll>(S, 0)));
    dp[P][P] = 1;

    for (int r = 0; r < m; ++r) {
      vector<vector<ll>> next(vector<vector<ll>>(S, vector<ll>(S, 0)));
      for (int i = 0; i < S; ++i) {
        for (int j = 0; j < S; ++j) {
          if (i > 0) next[i - 1][j] = (next[i - 1][j] + dp[i][j]) % MOD;
          if (i < S - 1) next[i + 1][j] = (next[i + 1][j] + dp[i][j]) % MOD;
          if (j > 0) next[i][j - 1] = (next[i][j - 1] + dp[i][j]) % MOD;
          if (j < S - 1) next[i][j + 1] = (next[i][j + 1] + dp[i][j]) % MOD;
        }
      }
      dp.swap(next);
    }

    ll ans = 0;
    for (int px = -50; px <= 150; ++px) {
      for (int py = -50; py <= 150; ++py) {
        ll tmp = 1;
        for (int i = 0; i < N; ++i) {
          int d = dist(x[i], y[i], px, py);
          if (d > m || (d - m) % 2 != 0) tmp = 0;
          tmp = (tmp * dp[px - x[i] + P][py - y[i] + P]) % MOD;
        }
        ans = (ans + tmp) % MOD;
      }
    }
    return (int)ans;
  }
};