Submission #1269748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269748		picrad	Bitaro the Brave (JOI19_ho_t1)	C++20	100 / 100	150 ms	141524 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],O[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--){
      I[i][j] = I[i-1][j] + I[i][j+1] - I[i-1][j+1];
      if(A[i][j] == 2)O[i]++;
      else if(A[i][j] == 1)J[j] += O[i];
      else I[i][j] += J[j];
    }
  }
  cout << I[H][1] << '\n';
}

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