Submission #554703

#TimeUsernameProblemLanguageResultExecution timeMemory
554703DrearyJokeBitaro the Brave (JOI19_ho_t1)C++17
100 / 100
77 ms89636 KiB
#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define END "\n"
#define rall(v) (v).rbegin(), (v).rend()
#define all(v) (v).begin(), (v).end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

void solve(){
    int h, w;
    cin >> h >> w;
    vector<string> A(h);
    for (int i = 0; i < h; ++i) cin >> A[i];
    vector<vector<int>> ccnt(h, vector<int>(w)), rcnt(h, vector<int>(w));
    for (int i = 0; i < h; ++i) {
        for (int j = w - 1; j >= 0; --j) {
            ccnt[i][j] = (j == w - 1 ? 0 : ccnt[i][j + 1]) + (A[i][j] == 'O');
        }
    }
    for (int i = h - 1; i >= 0; --i) {
        for (int j = 0; j < w; ++j) {
            rcnt[i][j] = (i == h - 1 ? 0 : rcnt[i + 1][j]) + (A[i][j] == 'I');
        }
    }
    ll ans = 0;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            ans += 1LL * (A[i][j] == 'J') * rcnt[i][j] * ccnt[i][j];
        }
    }
    cout << ans << END;
}
int main()
{
    fastio
    int t = 1;
    // cin>> t;
    while(t--) solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...