Submission #1351438

#TimeUsernameProblemLanguageResultExecution timeMemory
1351438cpismayilmmdv985Bitaro the Brave (JOI19_ho_t1)C++20
100 / 100
202 ms115744 KiB
#ifdef LOCAL
#include ".debug.hpp"
#else
#define debug(...) 42
#endif
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

signed main() {
#ifndef VOID
   cin.tie(nullptr)->sync_with_stdio(false);
#endif

   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<vector<int>>> suff(2, vector<vector<int>> (N + 5, vector<int> (M + 5)));
   // suff[0] -> O, suff[1] -> I 
   for (int i = 1; i <= N; i++)
      for (int j = M; j >= 1; j--)
         suff[0][i][j] = suff[0][i][j + 1] + (A[i][j] == 'O');
   for (int j = 1; j <= M; j++)
      for (int i = N; i >= 1; i--)
         suff[1][i][j] = suff[1][i + 1][j] + (A[i][j] == 'I');
   int64_t ans = 0;
   for (int i = 1; i <= N; i++)
      for (int j = 1; j <= M; j++)
         if (A[i][j] == 'J')  ans += 1LL * suff[0][i][j] * suff[1][i][j];
   cout << ans;
   
   return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...