제출 #1348374

#제출 시각아이디문제언어결과실행 시간메모리
1348374kantaponzBitaro the Brave (JOI19_ho_t1)C++20
100 / 100
248 ms169808 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int nx = 3005;

int h, w;
ll a[nx][nx], b[nx][nx]; // a = O <-, b = I ^
vector<pair<int,int>> qrs;
ll ans = 0;

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> h >> w;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            char x; cin >> x;
            if (x == 'O') a[i][j]++;
            else if (x == 'I') b[i][j]++;
            else qrs.emplace_back(i, j);
        }
    }

    for (int j = 1; j <= w; j++) {
        for (int i = h; i >= 1; i--) {
            b[i][j] += b[i + 1][j];
        }
    }

    for (int i = 1; i <= h; i++) {
        for (int j = w; j >= 1; j--) {
            a[i][j] += a[i][j + 1];
        }
    }

    for (auto [i, j] : qrs) {
        ans += a[i][j + 1] * b[i + 1][j];
    }

    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...