Submission #1275762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275762		rtri	Plus Minus (BOI17_plusminus)	C++20	12 / 100	1095 ms	4412 KiB

plusminus

#include <bits/stdc++.h>
using namespace std;

int n, m, k;
vector<vector<int>> grid;

int get(int y, int x) {
  if (0 <= y && 0 <= x && y < n && x < m)
    return grid[y][x];
  else {
    return 0;
  }
}

int df(int y, int x) {
  if (x == m)
    return 1;
  if (y == n)
    return df(0, x + 1);

  int ans = 0;
  if (grid[y][x] != -1) {
    if (0 == y || 0 == x ||
        get(y, x) + get(y - 1, x) + get(y - 1, x - 1) + get(y, x - 1) == 2)
      ans += df(y + 1, x);
  } else {
    grid[y][x] = 0;
    if (0 == y || 0 == x ||
        get(y, x) + get(y - 1, x) + get(y - 1, x - 1) + get(y, x - 1) == 2)
      ans += df(y + 1, x);
    grid[y][x] = 1;
    if (0 == y || 0 == x ||
        get(y, x) + get(y - 1, x) + get(y - 1, x - 1) + get(y, x - 1) == 2)
      ans += df(y + 1, x);
    grid[y][x] = -1;
  }
  return ans;
}

int powmod(int b, int e, int m) {
  b %= m;
  int res = 1;
  while (0 < e) {
    if (e & 1)
      res = (res * b) % m;
    b = (b * b) % m;
    e >>= 1;
  }
  return res;
}

int main() {
  cin >> n >> m >> k;

  grid.resize(n, vector<int>(m, -1));
  for (int i = 0; i < k; i++) {
    char pm;
    int y, x;
    cin >> pm >> y >> x;
    y--;
    x--;
    if (pm == '+')
      grid[y][x] = 1;
    else if (pm == '-')
      grid[y][x] = 0;
    else
      cerr << "BAD!" << "\n";
  }

  int ans = df(0, 0);

  cout << ans << endl;

  return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 42
• Subtask 3: 0 / 46