제출 #1301420

#제출 시각아이디문제언어결과실행 시간메모리
1301420tunademayoBitaro the Brave (JOI19_ho_t1)C++20
100 / 100
149 ms79816 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...