A - 勇者ビ太郎 (Bitaro the Brave) JOI 2018/2019 本選 過去問

問題

A - 勇者ビ太郎 (Bitaro the Brave)

考察

条件を充たすものをいちいち数えると計算量オーバーしそうなので、あらかじめ累積和的に数を数えておくことにしました。

制約の iがk より小さい　と　jがlより小さい　があるので難しいですが，大きい方から順に累積していくことで解決できそうです。

WAしたコード

書き上げてサンプルを通して提出しましたがWAに。

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

int on[3010][3010];
int in[3010][3010];

int main(){
  int H,W;
  cin>>H>>W;
  string S;
  char item[3010][3010];
  for(int i=0;i<H;i++){
    cin>>S;
    for(int j=0;j<W;j++){
      item[i][j]=S.at(j);
    }
  }
  
  //on[i][j]にi行のオーブの累積数を入力
  for(int i=0;i<H;i++){
    int temp=0;
    for(int j=W-1;j>=0;j--){
      if(item[i][j]=='O'){
        temp++;
        on[i][j]=temp;
      }
      else{
        if(j==W-1){
          on[i][j]=0;
        }
        else{
          on[i][j]=on[i][j+1];
        }
      }
    }
  }
  
  //in[i][j]にj列のインゴットの累積数を入力
  for(int j=0;j<W;j++){
    int temp=0;
    for(int i=H-1;i>=0;i--){
      if(item[i][j]=='I'){
        temp++;
        in[i][j]=temp;
      }
      else{
        if(i==H-1){
          in[i][j]=0;
        }
        else{
          in[i][j]=in[i+1][j];
        }
      }
    }
  }  
  int ans=0;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(item[i][j]=='J'){
        ans+=in[i][j]*on[i][j];
        //cout<<i<<" "<<j<<" "<<in[i][j]<<"*"<<on[i][j]<<endl;
      }
    }
  }
  /*for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cout<<in[i][j]<<" "<<on[i][j]<<" ";
    }
    cout<<endl;
  }*/
  
  cout<<ans<<endl;
  return 0;
}

ＡＣ

予想はどこかでＨとＷを間違えているか、オーバーフローです。

3000*3000の配列で９００万、積の個数で加算されるのでオーバーフローの可能性が高いと判断しました。

#define int long long して無事にACしました。