Submission #522650

#	Time	Username	Problem	Language	Result	Execution time	Memory
522650		Monarchuwu	Bitaro the Brave (JOI19_ho_t1)	C++17	100 / 100	231 ms	88456 KiB

joi2019_ho_t1

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

const int N = 3000 + 3;
int h, w;
char c[N][N];

int f[N][N], g[N][N];
void prep() {
    for (int i = 0; i < h; ++i)
        for (int j = w - 1; ~j; --j)
            f[i][j] = f[i][j + 1] + (c[i][j] == 'O');

    for (int j = 0; j < w; ++j)
        for (int i = h - 1; ~i; --i)
            g[i][j] = g[i + 1][j] + (c[i][j] == 'I');
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> h >> w;
    for (int i = 0; i < h; ++i) cin >> c[i];
    prep();

    ll ans(0);
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j)
            if (c[i][j] == 'J') ans += (ll)f[i][j] * g[i][j];
    cout << ans << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

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