Submission #369500

#	Time	Username	Problem	Language	Result	Execution time	Memory
369500		Nima_Naderi	Bitaro the Brave (JOI19_ho_t1)	C++14	100 / 100	320 ms	159596 KiB

joi2019_ho_t1

///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 3e3 + 10;
ll H, W, ans;
ll ps[MXN][MXN], sp[MXN][MXN];
string S[MXN];
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cin >> H >> W;
    for(int i = 1; i <= H; i ++){
        cin >> S[i], S[i] = "$" + S[i];
    }
    for(int i = 1; i <= H; i ++){
        for(int j = 1; j <= W; j ++){
            ps[i][j] = ps[i][j - 1] + (S[i][j] == 'O');
        }
    }
    for(int j = 1; j <= W; j ++){
        for(int i = 1; i <= H; i ++){
            sp[i][j] = sp[i - 1][j] + (S[i][j] == 'I');
        }
    }
    for(int i = 1; i <= H; i ++){
        for(int j = 1; j <= W; j ++){
            ll t1 = ps[i][W] - ps[i][j];
            ll t2 = sp[H][j] - sp[i][j];
            ans += t1 * t2 * (S[i][j] == 'J');
        }
    }
    cout << ans << '\n';
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

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