Submission #936937

#	Time	Username	Problem	Language	Result	Execution time	Memory
936937		detectivebowon	Bitaro the Brave (JOI19_ho_t1)	C++14	100 / 100	421 ms	188884 KiB

joi2019_ho_t1

#include<bits/stdc++.h>
using namespace std;
int h,w;
char space[3007][3007];
long long ans,qso[3007][3007],qsi[3007][3007];
queue<pair<int,int>> q;
int main()
{
    cin>>h>>w;
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)
        {
            cin>>space[i][j];
            if(space[i][j]=='J')
            {
                q.push({i,j});
            }
        }
    }
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)
        {
            if(space[i][j]=='I')
                qsi[i][j]=qsi[i-1][j]+1;
            else
                qsi[i][j]=qsi[i-1][j];
            if(space[i][j]=='O')
                qso[i][j]=qso[i][j-1]+1;
            else
                qso[i][j]=qso[i][j-1];
        }
    }
    while(!q.empty())
    {
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        ans+=(qsi[h][y]-qsi[x][y])*(qso[x][w]-qso[x][y]);
//        cout<<x<<" "<<y<<" "<<ans<<" "<<qsi[h][y]<<" "<<qso[x][w]<<"\n";
    }
    cout<<ans;
//    for(int i=1;i<=h;i++)
//    {
//        for(int j=1;j<=w;j++)
//        {
//            cout<<qsi[i][j]<<" ";
//        }
//        cout<<"\n";
//    }

}

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