Submission #889067

#	Time	Username	Problem	Language	Result	Execution time	Memory
889067		BBart888	Bitaro the Brave (JOI19_ho_t1)	C++14	100 / 100	246 ms	91460 KiB

joi2019_ho_t1

#include <bits/stdc++.h>

using namespace std;

const int MAXN= 3e3 + 11;

using  ll = long long;


int H,W;
string S[MAXN];
int cntI[MAXN][MAXN];
int cntO[MAXN][MAXN];
ll ans;

int main()
{
	cin.tie(0);
	cout.tie(0);
	
	cin >> H >> W;
	
	for(int i = 0;i<H;i++)
	{
		cin>>S[i];
	}
	
	
	for(int i =0;i<H;i++)
	{
		for(int j = 0;j<W;j++)
		{
			cntO[i][j]+=(S[i][j] == 'O');
		}
	}
	
	for(int i =0;i<H;i++)	
	{
		for(int j = W-1;j>=0;j--)
		{
			cntO[i][j]+=(cntO[i][j+1]);
		}
	}
	
	for(int i = H-1;i>=0;i--)
	{
		for(int j =0;j<W;j++)	
		{
			cntI[i][j] = (cntI[i+1][j] + (S[i][j] == 'I'));
		}
	}
	
	
	for(int i = 0;i<H;i++)
	{
		for(int j = 0;j<W;j++)
		{
			if(S[i][j] == 'J')
			{
				//cout<<i<<" "<<j<<" "<<cntI[i][j]<<" "<<cntO[i][j]<<'\n';
				ans+=(cntI[i][j]*cntO[i][j]);
			}
			//cout<<cntI[i][j]<<" ";
			
		}
		
	}
	
	cout<<ans<<'\n';
	
	return 0;
}

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