Submission #791876

#TimeUsernameProblemLanguageResultExecution timeMemory
791876BoomydayBitaro the Brave (JOI19_ho_t1)C++17
100 / 100
435 ms115192 KiB
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int H, W;
    cin >> H >> W;

    vector<vector<int>> grid;

    for (int i = 0; i < H; ++i) {
        string st;
        cin >> st;
        vector<int> row;
        for (int j = 0; j < W; ++j) {
            if (st[j] == 'J')
                row.push_back(0);
            else if (st[j] == 'O')
                row.push_back(1);
            else if (st[j] == 'I')
                row.push_back(2);
        }
        grid.push_back(row);
    }

    vector<vector<int>> grido(H + 1, vector<int>(W + 1, 0));
    vector<vector<int>> gridi(H + 1, vector<int>(W + 1, 0));

    // Calculate 'o' values
    for (int row = 0; row < H; ++row) {
        for (int col = W - 1; col >= 0; --col) {
            int num = (grid[row][col] == 1);
            grido[row][col] = grido[row][col + 1] + num;
        }
    }

    // Calculate 'i' values
    for (int col = 0; col < W; ++col) {
        for (int row = H - 1; row >= 0; --row) {
            int num = (grid[row][col] == 2);
            gridi[row][col] = gridi[row + 1][col] + num;
        }
    }

    long long ans = 0;

    for (int row = 0; row < H; ++row) {
        for (int col = 0; col < W; ++col) {
            if (grid[row][col] == 0) {
                ans += grido[row][col + 1] * gridi[row + 1][col];
            }
        }
    }

    cout << ans << endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...