Submission #757814

#	Time	Username	Problem	Language	Result	Execution time	Memory
757814		JANCARAPAN	Bitaro the Brave (JOI19_ho_t1)	C++17	100 / 100	308 ms	88696 KiB

joi2019_ho_t1

#include <bits/stdc++.h>
using namespace std;  
#define ll long long
#define fi first
#define se second
#define sz(a) (long long) a.size()
//#define endl '\n'

const long long INF = 1e18, MOD = 1e9+7;

void test_case() {
  int n, m;
  cin >> n >> m;
  vector a(n, vector<char>(m));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> a[i][j];
    }
  }
  vector suff_row(n, vector<int>(m)), suff_col(n, vector<int>(m));
  
  for (int i = 0; i < n; i++) {
    for (int j = m - 1; j >= 0; j--) {
      suff_row[i][j] = (j != m - 1 ? suff_row[i][j + 1] : 0) + (a[i][j] == 'O');
    }
  }
  for (int j = 0; j < m; j++) {
    for (int i = n - 1; i >= 0; i--) {
      suff_col[i][j] = (i != n - 1 ? suff_col[i + 1][j] : 0) + (a[i][j] == 'I');
    }
  }
  
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (a[i][j] != 'J') continue;
      ans += suff_row[i][j] * suff_col[i][j];
    }
  }
  cout << ans << endl;
}
 
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
    test_case();
  }
  return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50