Submission #557698

#	Time	Username	Problem	Language	Result	Execution time	Memory
557698		ljuba	Bitaro the Brave (JOI19_ho_t1)	C++17	100 / 100	236 ms	89640 KiB

joi2019_ho_t1

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<string> mat(n);
    for(auto &z : mat) cin >> z;

    vector<vector<int>> ig(n, vector<int>(m, 0));
    vector<vector<int>> o(n, vector<int>(m, 0));

    for(int i = n-1; i >= 0; --i) {
        for(int j = 0; j < m; ++j) {
            ig[i][j] = (mat[i][j] == 'I');

            if(i + 1 < n) {
                ig[i][j] += ig[i+1][j];
            }
        }
    }

    for(int j = m-1; j >= 0; --j) {
        for(int i = 0; i < n; ++i) {
            o[i][j] = (mat[i][j] == 'O');

            if(j + 1 < m) {
                o[i][j] += o[i][j+1];
            }
        }
    }

    ll ans = 0;

    for(int i = 0; i + 1 < n; ++i) {
        for(int j = 0; j + 1 < m; ++j) {
            if(mat[i][j] != 'J') continue;
            ans += ig[i+1][j] * o[i][j+1];
        }
    }

    cout << ans << '\n';
}

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