惑星探査 (Planetary Exploration) 第 10 回日本情報オリンピック 2010/2011 本選 第１問

https://www.ioi-jp.org/joi/2010/2011-ho-tasks_data/2011-ho.pdf#page=2

二次元累積和の問題が続きます。
わりとスムーズに書けましたが２０分ほどかかりました。

#include <bits/stdc++.h>
using namespace std;

int MDN[1010][1010][3];

int main(){
  int M,N,K;
  cin>>M>>N>>K;
  
  //地形データ入力
  string temp;
  for(int i=1;i<=M;i++){
    cin>>temp;
    for(int j=0;j<N;j++){ 
      if(temp.at(j)=='J'){
        MDN[i][j+1][0]=1;
      }
    
      if(temp.at(j)=='O'){
        MDN[i][j+1][1]=1;
      }
      if(temp.at(j)=='I'){
        MDN[i][j+1][2]=1;        
      }      
    }
         
  }
  
  //累積和入力　AMD[i][j][3] 0 - J 1 - O I - 2
  int AMD[1010][1010][3];
  for(int i=1;i<=M;i++){
    for(int j=1;j<=N;j++){
      AMD[i][j][0]=AMD[i][j-1][0]+AMD[i-1][j][0]+MDN[i][j][0]-AMD[i-1][j-1][0];
      AMD[i][j][1]=AMD[i][j-1][1]+AMD[i-1][j][1]+MDN[i][j][1]-AMD[i-1][j-1][1];   
      AMD[i][j][2]=AMD[i][j-1][2]+AMD[i-1][j][2]+MDN[i][j][2]-AMD[i-1][j-1][2];
    }
  }
  int a,b,c,d;
  int ans1,ans2,ans3;
  for(int i=0;i<K;i++){
    cin>>a>>b>>c>>d;
    ans1=AMD[c][d][0]-AMD[c][b-1][0]-AMD[a-1][d][0]+AMD[a-1][b-1][0];
    ans2=AMD[c][d][1]-AMD[c][b-1][1]-AMD[a-1][d][1]+AMD[a-1][b-1][1];
    ans3=AMD[c][d][2]-AMD[c][b-1][2]-AMD[a-1][d][2]+AMD[a-1][b-1][2];
    cout<<ans1<<" "<<ans2<<" "<<ans3<<endl;
  }
  return 0;
}