Submission #1359681

#TimeUsernameProblemLanguageResultExecution timeMemory
1359681Yusif_NazarliBitaro the Brave (JOI19_ho_t1)C++20
100 / 100
293 ms150616 KiB
#pragma GCC optimize("O3")
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
 
#define int long long
#define all(v) v.begin() , v.end()
#define rall(v) v.rbegin() , v.rend()
#define pii pair<int , int>
#define pb push_back
#define F first 
#define S second
using namespace std;
using namespace __gnu_pbds;
 
const int N = 2e5 + 1000;
const int mod = 998244353;
const int inf = 1e18;
const int LOG = 20;

void Yusiff(){
  int n , m; cin >> n >> m;
  vector<vector<char>> a(n + 1 , vector<char>(m + 1));
  int ans = 0;
  vector<int> used(n + 1 , 0);
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      cin >> a[i][j];
      if(a[i][j] == 'O') used[i]++;
    }
  }
  vector<vector<int>> pref(n + 1 , vector<int>(m + 1 , 0));
  for(int i = 1; i <= n; i++){
    pref[i][1] = 0;
    pref[i][0] = 0;
    for(int j = 1; j <= m; j++){
      if(a[i][j] == 'O'){
        pref[i][j] = pref[i][j - 1] + 1;
      } else pref[i][j] = pref[i][j - 1];
    }
  }
  vector<vector<int>> pref1(n + 1 , vector<int>(m + 1 , 0));
  for(int j = 1; j <= m; j++){
    for(int i = 1; i <= n; i++){
      if(a[i][j] == 'I') pref1[i][j] = pref1[i - 1][j] + 1;
      else pref1[i][j] = pref1[i - 1][j];
    }
  }
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      if(a[i][j] == 'J'){
        int cnt = pref1[n][j] - pref1[i - 1][j];
        int cnt1 = pref[i][m] - pref[i][j - 1];
        ans += cnt * cnt1;
      }
    }
  }
  cout << ans << '\n';
}

signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);  
  
  // freopen("mountains.in" , "r" , stdin);
  // freopen("mountains.out" , "w" , stdout);

  int T = 1;
  // cin >> T;
  while(T--){
    Yusiff();
  }
}

/*

0 0 1

*/
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...