Submission #1297956

#TimeUsernameProblemLanguageResultExecution timeMemory
1297956chithanhnguyenBitaro the Brave (JOI19_ho_t1)C++20
100 / 100
107 ms79840 KiB
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define ld long double
#define pii pair<int, int>
#define fi first
#define se second
#define __builtin_popcount __builtin_popcountll
#define all(x) (x).begin(), (x).end()
#define BIT(x, i) (((x) >> (i)) & 1)

#define debug(a, l, r) for (int i = (l); i <= (r); ++i) cout << (a)[i] << ' '; cout << '\n';

const int MAXN = 3005;
int n, m, valO[MAXN][MAXN], valI[MAXN][MAXN];
char grid[MAXN][MAXN];

void init() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        string s; cin >> s;
        s = ' ' + s;
        for (int j = 1; j <= m; ++j) {
            grid[i][j] = s[j];
            valO[i][j] = (s[j] == 'O');
            valI[i][j] = (s[j] == 'I');
        }
    }

    // Build prefix sum
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            valO[i][j] += valO[i - 1][j] + valO[i][j - 1] - valO[i - 1][j - 1];
            valI[i][j] += valI[i - 1][j] + valI[i][j - 1] - valI[i - 1][j - 1];
        }
    }
}

void solve() {
    long long res = 0;
    for (int i = 1; i < n; ++i) {
        for (int j = 1; j < m; ++j) {
            if (grid[i][j] != 'J') continue;
            // cout << "J at " << i << ", " << j << '\n';
            int choiceO = valO[i][m] - valO[i - 1][m] - valO[i][j - 1] + valO[i - 1][j - 1];
            int choiceI = valI[n][j] - valI[n][j - 1] - valI[i - 1][j] + valI[i - 1][j - 1];
            res += 1ll * choiceO * choiceI;
            // cout << choiceO << ' ' << choiceI << '\n';
        }
    }

    cout << res;
}

signed main() {
    #ifdef NCTHANH
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    init(); 
    solve();

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...