#include<bits/stdc++.h>
using namespace std;
#define ll long long
const bool Multitest = 0;
const int N = 3005;
char a[N][N];
int f[3][N][N]; char b[N];
int n, m;
int sum(int x, int i, int j, int u, int v)
{
return f[x][u][v] - f[x][u][j - 1] - f[x][i - 1][v] + f[x][i - 1][j - 1];
}
void work()
{
cin >> n >> m;
b[0] = 'J';
b[1] = 'O';
b[2] = 'I';
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ; j <= m ; j++)
{
cin >> a[i][j];
}
}
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ; j <= m ; j++)
{
for(int x = 1 ; x < 3 ; x++)
{
f[x][i][j] = f[x][i - 1][j] + f[x][i][j - 1] - f[x][i - 1][j - 1];
f[x][i][j] += (b[x] == a[i][j]);
}
}
}
// for(int x = 0 ; x < 3 ; x++)
// {
// for(int i = 1 ; i <= n ; i++)
// {
// for(int j = 1 ; j <= m ; j++)
// {
// cerr << f[x][i][j] << ' ';
// } cerr << '\n';
// }
// cerr << '\n';
// cerr << '\n';
// }
ll ans = 0;
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ; j <= m ; j++)
{
if(a[i][j] == 'J')
{
ans += 1ll * sum(1, i, j, i, m) * sum(2, i, j, n, j);
}
}
}
cout << ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int q = 1;
if(Multitest) cin >> q;
while(q--) work();
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |