제출 #114792

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
114792		andreiomd	Bitaro the Brave (JOI19_ho_t1)	C++11	100 / 100	138 ms	88760 KiB

joi2019_ho_t1

#include <iostream>

using namespace std;

const int NMAX = 3e3 + 5;

int N, M;

char A[NMAX][NMAX];

int O[NMAX][NMAX], I[NMAX][NMAX];

long long ans = 0;

inline void Read ()
{
    ios_base :: sync_with_stdio(false);

    cin.tie(NULL);

    cin>>N>>M;

    for(int i = 1; i <= N; ++i)
        cin>>(A[i] + 1);

    return;
}

inline void Precalculation ()
{
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
        {
            O[i][j] = O[i-1][j] + O[i][j-1] - O[i-1][j-1] + (A[i][j] == 'O');

            I[i][j] = I[i-1][j] + I[i][j-1] - I[i-1][j-1] + (A[i][j] == 'I');
        }

    return;
}

inline int Query1 (int X1, int Y1, int X2, int Y2)
{
    return O[X2][Y2] - O[X2][Y1-1] - (O[X1-1][Y2] - O[X1-1][Y1-1]);
}

inline int Query2 (int X1, int Y1, int X2, int Y2)
{
    return I[X2][Y2] - I[X2][Y1-1] - (I[X1-1][Y2] - I[X1-1][Y1-1]);
}

int main()
{
    Read();

    Precalculation();

    for(int i = 1; i < N; ++i)
        for(int j = 1; j < M; ++j)
            if(A[i][j] == 'J')
            {
                long long p1 = Query1(i, j + 1, i, M);

                long long p2 = Query2(i + 1, j, N, j);

                ans += 1LL * p1 * p2;
            }

    cout<<ans<<'\n';

    return 0;
}

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