Submission #961013

---

Source Code Expand

#include <string>
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

int M = 1000000007;

bool check (int x, int y, int W, int H) {
  return 0 <= x && x < W && 0 <= y && y < H;
}

int count (std::vector<int> const & a, std::vector<int> & memo, int x, int y, int W, int H) {
  if (memo[x + W * y] >= 0) {
    return memo[x + W * y];
  }
  int total = 1;
  if (check(x - 1, y, W, H) && (a[x + W * y] > a[x - 1 + W * y])) {
    total = (total + count(a, memo, x - 1, y , W, H)) % M;
  }
  if (check(x + 1, y, W, H) && (a[x + W * y] > a[x + 1 + W * y])) {
    total = (total + count(a, memo, x + 1, y , W, H)) % M;
  }
  if (check(x, y - 1, W, H) && (a[x + W * y] > a[x + W * (y - 1)])) {
    total = (total + count(a, memo, x, y - 1, W, H)) % M;
  }
  if (check(x, y + 1, W, H) && (a[x + W * y] > a[x + W * (y + 1)])) {
    total = (total + count(a, memo, x, y + 1, W, H)) % M;
  }
  memo[x + W * y] = total;
  return total;
}

int main (int argc, char ** argv) {
  std::string line;
  std::getline(std::cin, line);

  char * ptr1 = &line[0];
  char * ptr2;
  int H = std::strtol(ptr1, &ptr2, 10);
  ptr1 = ptr2;
  int W = std::strtol(ptr1, &ptr2, 10);

  std::vector<int> a(W * H, 0);
  std::vector<std::tuple<int, int, int>> b(W * H);
  std::vector<int> memo(W * H, -1);

  for (int y = 0; y < H; ++y) {
    std::getline(std::cin, line);
    char * ptr1 = &line[0];
    char * ptr2;
    for (int x = 0; x < W; ++x) {
      int z = std::strtol(ptr1, &ptr2, 10);
      a[x + W * y] = z;
      b[x + W * y] = std::tuple<int, int, int>(x, y, z);
      ptr1 = ptr2;
    }
  }

  std::sort(b.begin(), b.end(), [] (auto l, auto r) { return std::get<2>(l) < std::get<2>(r); });

  int total = 0;
  for (auto const & v : b) {
    total = (total + count(a, memo, std::get<0>(v), std::get<1>(v), W, H)) % M;
  }
  std::cout << total << std::endl;
}

Submission Info

Judge Result