Submission #713012

#	Time	Username	Problem	Language	Result	Execution time	Memory
713012		thimote75	Bitaro the Brave (JOI19_ho_t1)	C++14	100 / 100	422 ms	153436 KiB

joi2019_ho_t1

#include <bits/stdc++.h>

using namespace std;

#define num long long

const int W = 3000;
const int H = W;

num dp0[W][H];
num dp1[W][H];
bool dp2[W][H];

int main () {
    int w, h;
    cin >> w >> h;

    for (int i = 0; i < w; i ++) {
        string b;
        cin >> b;

        for (int j = 0; j < h; j ++) {
            if (b[j] == 'J') dp2[i][j] = true;
            if (b[j] == 'O') dp1[i][j] = 1;
            if (b[j] == 'I') dp0[i][j] = 1;
        }
    }

    for (int i = w - 2; i >= 0; i --)
        for (int j = 0; j < h; j ++)
            dp0[i][j] += dp0[i + 1][j];
    for (int j = h - 2; j >= 0; j --)
        for (int i = 0; i < w; i ++)
            dp1[i][j] += dp1[i][j + 1];
    
    num ans = 0;
    for (int i = 0; i < w; i ++)
        for (int j = 0; j < h; j ++)
            if (dp2[i][j])
                ans += dp0[i][j] * dp1[i][j];
    
    cout << ans;
}

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