Submission #210027

#	Time	Username	Problem	Language	Result	Execution time	Memory
210027		ld_minh4354	Bitaro the Brave (JOI19_ho_t1)	C++14	100 / 100	408 ms	160284 KiB

joi2019_ho_t1

#include<bits/stdc++.h>
using namespace std;

long long int m,n,i,j,dp1[3010][3010],dp2[3010][3010],ans;
string s[3010];

signed main()
{
    ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>m>>n;
	for (i=1;i<m+1;i++) cin>>s[i-1];
	for (i=1;i<m+1;i++)
	{
		dp1[i][n]=0;
		for (j=n-1;j>0;j--)
		if (s[i-1][j]=='O') dp1[i][j]=dp1[i][j+1]+1;
		else dp1[i][j]=dp1[i][j+1];
	}
	for (i=1;i<n+1;i++)
	{
		dp2[m][i]=0;
		for (j=m-1;j>0;j--)
		if (s[j][i-1]=='I') dp2[j][i]=dp2[j+1][i]+1;
		else dp2[j][i]=dp2[j+1][i];
	}
	ans=0;
	for (i=1;i<m+1;i++) for (j=1;j<n+1;j++) if (s[i-1][j-1]=='J')
	ans=ans+dp1[i][j]*dp2[i][j];
	cout<<ans;
}

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