Submission #1359218

#TimeUsernameProblemLanguageResultExecution timeMemory
1359218tuncay_pashaBitaro the Brave (JOI19_ho_t1)C++20
100 / 100
147 ms150592 KiB
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define pasha ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(v) begin(v), end(v)
using namespace std;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

constexpr int N = 1e+5 + 5, oo = 2e+18;

void _() {
  int n, m; cin >> n >> m;
  vector<vector<char>> a(n + 1, vector<char>(m + 1));
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      cin >> a[i][j];
    }
  }
  vector<vector<int>> pref1(n + 1, vector<int>(m + 1, 0));
  vector<vector<int>> pref2(n + 1, vector<int>(m + 1, 0));
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      pref1[i][j] = pref1[i - 1][j] + pref1[i][j - 1] - pref1[i - 1][j - 1] + (a[i][j] == 'O');
      pref2[i][j] = pref2[i - 1][j] + pref2[i][j - 1] - pref2[i - 1][j - 1] + (a[i][j] == 'I');
    }
  }
  auto ask = [&](int l1, int r1, int l2, int r2) -> pair<int, int> {
    int cnto = pref1[l2][r2] - pref1[l2][r1 - 1] - pref1[l1 - 1][r2] + pref1[l1 - 1][r1 - 1];
    int cnti = pref2[l2][r2] - pref2[l2][r1 - 1] - pref2[l1 - 1][r2] + pref2[l1 - 1][r1 - 1];
    return {cnto, cnti};
  };
  // return;
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (a[i][j] != 'J') {
        continue;
      }
      pair<int, int> p1 = ask(i, j, i, m);
      pair<int, int> p2 = ask(i, j, n, j);
      ans += p1.ff * p2.ss;
      // cout << p1.ff << ' ' << p2.ss << '\n';
    }
  }
  cout << ans << '\n';
}

signed main() {
  pasha
  int t = 1;
  // cin >> t;
  for (int cs = 1; cs <= t; ++cs) {
    _();
    // cout << '\n';
  }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...