Submission #1269744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269744		picrad	Bitaro the Brave (JOI19_ho_t1)	C++20	50 / 100	205 ms	282680 KiB

joi2019_ho_t1

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
typedef double dbl;
typedef pair<ll,ll> pii;
 
const int maxn = 3e3+5,MOD = 1e9+7;
ll H,W,A[maxn][maxn];
ll J[maxn][maxn],O[maxn][maxn],I[maxn][maxn];
string S;
 
int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> H >> W;
  for(int i =1; i <= H; i++){
    cin >> S;
    for(int j=1; j <= W;j++ ){
      if(S[j-1] == 'J') A[i][j] = 1;
      else if(S[j-1] == 'O') A[i][j] = 2;
      else A[i][j] = 3;
    }
  }
  for(int i =1; i <= H; i++){
    for(int j = W; j > 0; j--){
      O[i][j] = O[i][j+1];
      J[i][j] = J[i-1][j];
      I[i][j] = I[i-1][j] + I[i][j+1] - I[i-1][j+1];
      if(A[i][j] == 2)O[i][j]++;
      else if(A[i][j] == 1)J[i][j] += O[i][j+1];
      else I[i][j] += J[i-1][j];
    }
  }
  cout << I[H][1] << '\n';
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 0 / 50