Submission #301966

#	Time	Username	Problem	Language	Result	Execution time	Memory
301966		MylnikovNikolay	Bitaro the Brave (JOI19_ho_t1)	C++17	100 / 100	426 ms	150520 KiB

joi2019_ho_t1

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair <ll , ll> pll;

#define fi first
#define se second
//#define int ll

const int intf = 2e9 , maxn = 1e5 + 5;
const ll inf = 2e18 , mod = 1e9 + 7;


void solve(){
    int h , w;
    cin >> h >> w;
    vector < vector <int> > a;
    vector < vector <int> > pref[3];
    a = pref[0] = pref[1] = pref[2] = vector < vector <int> > (h , vector <int> (w , 0));
    for (int i = 0; i < h; i ++){
        for (int j = 0; j < w; j ++){
            char c; cin >> c;
            if (c == 'J'){
                a[i][j] = 0;
            } else if (c == 'O'){
                a[i][j] = 1;
                pref[1][i][j] = 1;
            } else {
                a[i][j] = 2;
                pref[2][i][j] = 1;
            }
        }
    }

    for (int i = h - 1; i >= 0; i --){
        for (int j = w - 1; j >= 0; j --){
            if (j + 1 < w)
                pref[1][i][j] += pref[1][i][j + 1];
            if (i + 1 < h)
                pref[2][i][j] += pref[2][i + 1][j];
        }
    }

    ll ans = 0;
    for (int i = 0; i < h; i ++){
        for (int j = 0; j < w; j ++){
            if (a[i][j] != 0)
                continue;
            ans += pref[1][i][j] * pref[2][i][j];
        }
    }

    cout << ans << '\n';

}

signed main() {
    //freopen("input.txt" , "r" , stdin);
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout.precision(20);

    int t = 1; //cin >> t;
    while(t-->0){
        solve();
    }

	return 0;
}

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