제출 #1092378

#제출 시각아이디문제언어결과실행 시간메모리
1092378FlandreBitaro the Brave (JOI19_ho_t1)C++14
100 / 100
460 ms81048 KiB
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
 
const int NMAX = 3069;
 
int vals[NMAX][NMAX];
int oscores[NMAX][NMAX];
bool iexist[NMAX];
bool jexist[NMAX];
 
int main() {
  int I, J;
  cin >> I >> J;
 
  for (int i = 1; i <= I; i++) {
    for (int j = 1; j <= J; j++) {
      char v;
      cin >> v;
      
      if (v == 'J') {
        vals[i][j] = 1;
        iexist[i] = true;
        jexist[j] = true;
      } else if (v == 'I') {
        vals[i][j] = 2;
      } else {
        vals[i][j] = 3;
      }
    }
  }
 
  for (int i = I - 1; i > 0; i--) {
    if (!iexist[i]) continue;
    ll oscore = 0;
    for (int j = J; j > 0; j--) {
      if (vals[i][j] == 3) {
        oscore++;
      }
      oscores[i][j] = oscore;
    } 
  }
 
 
  // for (int i = 1; i <= I; i++) {
  //   for (int j = 1; j <= J; j++) {
  //     cout << oscores[i][j];
  //   }
  //   cout << endl;
  // }
 
  ll possibilities = 0;
 
  for (int j = J - 1; j > 0; j--) {
    if (!jexist[j]) continue;
    ll iscore = 0;
    for (int i = I; i > 0; i--) {
      if (vals[i][j] == 2) {
        iscore++;
      }
      if (vals[i][j] == 1) {
        possibilities += iscore * oscores[i][j];
      }
    } 
  }
 
  cout << possibilities << endl;
 
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...