Ruudukko

#include <iostream>
#include <vector>
#include <set>

using namespace std;
int n;
string board[1000];

vector<int> mergeAndMakeUnique(vector<int> &a, vector<int> &b) {
  set<int> s;

  for (int x : a) s.insert(x);
  for (int x : b) s.insert(x);

  vector<int> v ( s.begin(), s.end() );
  return v;
}

void increaseByOne(vector<int> &a) {
  for (int i = a.size() - 1; i > -1; i--) a[i]++;
}

int main() {
  cin >> n;
  vector<vector<vector<int>>> grid(n, vector<vector<int>>(n));

  for (int i = 0; i < n; i++) {
    cin >> board[i];
  }

  int coins = 0;
  for (int i = 0; i < n; i++) {
    if (board[0][i] == 'o') coins++;
    grid[0][i].push_back(coins);
  }

  for (int i = 1; i < n; i++) {
    if (board[i][0] == 'o') {
      grid[i][0].push_back(grid[i-1][0][0]+1);
    } else {
      grid[i][0].push_back(grid[i-1][0][0]);
    }
  }

  for (int i = 1; i < n; i++) {
    for (int j = 1; j < n; j++) {
      grid[i][j] = mergeAndMakeUnique(grid[i][j-1], grid[i-1][j]);
      if (board[i][j] == 'o') {
        increaseByOne(grid[i][j]);
      }
    }
  }

  cout << grid[n-1][n-1].size();
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

Test 7

Group: 2, 3

Verdict: ACCEPTED

Test 8

Group: 2, 3

Verdict: ACCEPTED

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 2, 3

Verdict: ACCEPTED

Test 11

Group: 2, 3

Verdict: ACCEPTED

Test 12

Group: 2, 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 3

Verdict: ACCEPTED