Submission #1083749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083749		Flandre	Bitaro the Brave (JOI19_ho_t1)	C++17	100 / 100	489 ms	81236 KiB

joi2019_ho_t1

#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;
}

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