Submission #885644

#	Time	Username	Problem	Language	Result	Execution time	Memory
885644		goodspeed0208	Bitaro the Brave (JOI19_ho_t1)	C++14	100 / 100	257 ms	161616 KiB

joi2019_ho_t1

#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";
}

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