Submission #885644

#TimeUsernameProblemLanguageResultExecution timeMemory
885644goodspeed0208Bitaro the Brave (JOI19_ho_t1)C++14
100 / 100
257 ms161616 KiB
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#define int long long
#define INF 10000000000000000
#define MOD 1000000007
#define pii pair<long long, long long>
using namespace std;

signed main() {
	int n, m;
	cin >> n >> m;
	vector<string>s(n);
	for (auto &i : s) {
		cin >> i;
	}
	vector<vector<pii> >dp(n+1, vector<pii>(m+1, {0, 0}));
	for (int i = n-1 ; i >= 0 ; i--) {
		for (int j = m-1 ; j >= 0 ; j--) {
			dp[i][j] = {dp[i][j+1].first, dp[i+1][j].second};
			if (s[i][j] == 'O') dp[i][j].first++;
			else if (s[i][j] == 'I') dp[i][j].second++;
		}
	}
	int ans = 0;
	for (int i = 0 ; i < n ; i++) {
		for (int j = 0 ; j < m ; j++) {
			//cout << dp[i][j].first << " ";
			if (s[i][j] == 'J') ans += dp[i][j].first * dp[i][j].second;
		}
		//cout << "\n";
	}
	cout << ans << "\n";
}












#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...