제출 #1263952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1263952		thewizardman	Bitaro the Brave (JOI19_ho_t1)	C++20	100 / 100	248 ms	98988 KiB

joi2019_ho_t1

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using ll = long long;

int n, m, O[3000][3000], I[3000][3000];
ll ans;
string s;
vector<pii> J;

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> s;
    for (int j = 0; j < m; j++) {
      if (s[j] == 'J') J.push_back({i, j});
      else if (s[j] == 'O') O[i][j]++;
      else if (s[j] == 'I') I[i][j]++;
    }
  }
  for (int i = 0; i < n; i++) for (int j = m-1; j > 0; j--) {
    int l = (j & (j+1)) - 1;
    if (l >= 0) O[i][l] += O[i][j];
  }
  for (int j = 0; j < m; j++) for (int i = n-1; i > 0; i--) {
    int l = (i & (i+1)) - 1;
    if (l >= 0) I[l][j] += I[i][j];
  }
  for (const auto &[x, y]: J) {
    int a = 0, b = 0;
    for (int j = y; j < m; j = j | (j+1)) a += O[x][j];
    for (int i = x; i < n; i = i | (i+1)) b += I[i][y];
    ans += (ll) a * b;
  }
  cout << ans;
}

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