Submission #1349988

#TimeUsernameProblemLanguageResultExecution timeMemory
1349988ElayV13Bitaro the Brave (JOI19_ho_t1)C++20
100 / 100
157 ms149960 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int INF=1e18;

int n,m;
char a[3001][3001];
int pI[3001][3001];
int pO[3001][3001];

int getI(int col,int l,int r){
      return pI[col][r]-pI[col][l-1];
}
int getO(int row,int l,int r){
      return pO[row][r]-pO[row][l-1];
}

void solve(){
      cin>>n>>m;
      for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                  cin>>a[i][j];
            }
      }
      for(int i=0;i<m;i++){
            pI[i][0]=(a[i][0]=='I');
            for(int j=1;j<n;j++) pI[i][j]=pI[i][j-1]+(a[j][i]=='I');
      }
      for(int i=0;i<n;i++){
            pO[i][0]=(a[i][0]=='O');
            for(int j=1;j<m;j++) pO[i][j]=pO[i][j-1]+(a[i][j]=='O');
      }
      int res=0;
      for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                  if(a[i][j]!='J') continue;
                  int cnt1=getI(j,i+1,n-1);
                  int cnt2=getO(i,j+1,m-1);
                  res+=(cnt1*cnt2);
            }
      }
      cout<<res<<endl;
}
signed main(){
      ios_base::sync_with_stdio(false);
      cin.tie(nullptr);
      cout.tie(nullptr);
      int T=1;//cin>>T;
      while(T--) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...