提出 #72575913

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include<atcoder/modint>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <boost/multiprecision/cpp_dec_float.hpp>
using namespace std;
using ll=long long;
using ldub=long double;
using str=string;
using tup2=tuple<ll,ll>;
using tup3=tuple<ll,ll,ll>;
using tup4=tuple<ll,ll,ll,ll>;
using tup5=tuple<ll,ll,ll,ll,ll>;
using tup6=tuple<ll,ll,ll,ll,ll,ll>;
using tup7=tuple<ll,ll,ll,ll,ll,ll,ll>;
using tupcl=tuple<char,ll>;
using vec=vector<ll>;
using vec2=vector<vec>;
using vec3=vector<vec2>;
using vec4=vector<vec3>;
using vec5=vector<vec4>;
using vec6=vector<vec5>;
using vecs=vector<str>;
using vecs2=vector<vecs>;
using vecc=vector<char>;
using vecc2=vector<vecc>;
using vect2=vector<tup2>;
using vect3=vector<tup3>;
using vect4=vector<tup4>;
using vect5=vector<tup5>;
using vectcl=vector<tupcl>;
using que=queue<ll>;
using que2=queue<tup2>;
using que3=queue<tup3>;
using que4=queue<tup4>;
using que5=queue<tup5>;
using que6=queue<tup6>;
using que7=queue<tup7>;
using Pque=priority_queue<ll>;
using pque=priority_queue<ll,vec,greater<ll>>;
using Pque2=priority_queue<tup2>;
using pque2=priority_queue<tup2,vect2,greater<tup2>>;
using Pque3=priority_queue<tup3>;
using pque3=priority_queue<tup3,vect3,greater<tup3>>;
using Pque4=priority_queue<tup4>;
using pque4=priority_queue<tup4,vect4,greater<tup4>>;
using Pque5=priority_queue<tup5>;
using pque5=priority_queue<tup5,vect5,greater<tup5>>;
//using namespace boost::multiprecision;
//using lll=cpp_int;
//using longf=cpp_dec_float_100;

#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define ins insert
#define tup make_tuple
#define low lower_bound
#define pops(a) __builtin_popcountll(a)
#define all(v) v.begin(),v.end()
#define perm(v) next_permutation(all(v))
#define INF (ll)4e18
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define YN(f) cout << ((f)?"Yes":"No") << endl

int main(){
  ll H,W;
  cin >> H >> W;
  vecc2 M(H,vecc(W));
  for(ll i=0;i<H;i++){
    for(ll j=0;j<W;j++) cin >> M[i][j];
  }
  vec2 dp(H,vec(W)),F(H,vec(W)),G(H,vec(W));
  for(ll i=0;i<H;i++){
    for(ll j=0;j<W;j++){
      if(M[i][j]=='F') F[i][j]++;
      if(M[i][j]=='G') G[i][j]++;
    }
  }
  for(ll i=0;i<H;i++){
    for(ll j=W-1;j>=0;j--){
      if(i!=0) F[i][j]+=F[i-1][j];
      if(j!=W-1) F[i][j]+=F[i][j+1];
      if(i!=0&&j!=W-1) F[i][j]-=F[i-1][j+1];
    }
  }
  for(ll i=H-1;i>=0;i--){
    for(ll j=0;j<W;j++){
      if(i!=H-1) G[i][j]+=G[i+1][j];
      if(j!=0) G[i][j]+=G[i][j-1];
      if(i!=H-1&&j!=0) G[i][j]-=G[i+1][j-1];
    }
  }
  for(ll i=H-2;i>=0;i--){
    for(ll j=W-2;j>=0;j--){
      dp[i][j]=dp[i][j+1]+dp[i+1][j]-dp[i+1][j+1];
      ll f,g;
      if(i!=0) f=F[i][j+1]-F[i-1][j+1];
      else f=F[i][j+1];
      if(j!=0) g=G[i+1][j]-G[i+1][j-1];
      else g=G[i+1][j];
      dp[i][j]+=f*g;
    }
  }
  ll ans=0;
  for(ll i=0;i<H-1;i++){
    for(ll j=0;j<W-1;j++){
      if(M[i][j]=='E') ans+=dp[i+1][j+1];
    }
  }
  cout << ans << endl;
}

提出情報

ジャッジ結果