Submission #294903

#	Time	Username	Problem	Language	Result	Execution time	Memory
294903		dolijan	Bitaro the Brave (JOI19_ho_t1)	C++14	100 / 100	696 ms	189420 KiB

joi2019_ho_t1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mn=3069;
int a[mn][mn];
ll red[mn][mn];
ll kolona[mn][mn];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        string s;
        cin>>s;
        for(int j=0;j<m;j++)
        {
            if(s[j]=='J') a[i][j]=0;
            else if(s[j]=='O') a[i][j]=1;
            else a[i][j]=2;
        }
    }
    ll kolko=0;
    for(int i=0;i<m;i++)
    {
        if(a[0][i]==2) red[0][i]=1;
    }
    for(int i=0;i<n;i++)
    {
        if(a[i][0]==1) kolona[i][0]=1;
    }
    for(int i=0;i<n;i++)
    {
        for(int j=1;j<m;j++)
        {
            kolona[i][j]=kolona[i][j-1];
            if(a[i][j]==1) kolona[i][j]++;
            //cout<<kolona[i][j]<<" ";
        }
        //cout<<endl;
    }
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            red[i][j]=red[i-1][j];
            if(a[i][j]==2) red[i][j]++;
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(a[i][j]==0)
            {
                /*cout<<i<<" "<<j<<endl;
                cout<<kolona[i][m-1]<<" "<<kolona[i][j]<<endl;
                cout<<red[n-1][j]<<" "<<red[i][j]<<endl;*/
                kolko+=((kolona[i][m-1]-kolona[i][j])*(red[n-1][j]-red[i][j]));
            }
        }
    }
    cout<<kolko<<endl;
}

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