Submission #858865

#TimeUsernameProblemLanguageResultExecution timeMemory
858865StefanSebezBitaro the Brave (JOI19_ho_t1)C++14
100 / 100
271 ms190044 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int pref[4][3050][3050];
signed main()
{
    int n,m;cin>>n>>m;
    int a[n+1][m+1];
    for(int i=1;i<=n;i++)
	{
		string s;cin>>s;
		for(int j=0;j<m;j++)
		{
			if(s[j]=='J') a[i][j+1]=0;
			if(s[j]=='O') a[i][j+1]=1;
			if(s[j]=='I') a[i][j+1]=2;
		}
	}
	memset(pref,0,sizeof(pref));
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			for(int k=0;k<=2;k++) pref[k][i][j]=pref[k][i-1][j]+pref[k][i][j-1]-pref[k][i-1][j-1];
			pref[a[i][j]][i][j]++;
		}
	}
	ll res=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]!=0) continue;
			ll x=pref[1][i][m]-pref[1][i-1][m]-pref[1][i][j]+pref[1][i-1][j];
			ll y=pref[2][n][j]-pref[2][n][j-1]-pref[2][i][j]+pref[2][i][j-1];
			res+=x*y;
		}
	}
	cout<<res;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...