Submission #897197

#	Time	Username	Problem	Language	Result	Execution time	Memory
897197		aqxa	Bitaro the Brave (JOI19_ho_t1)	C++17	100 / 100	164 ms	89628 KiB

joi2019_ho_t1

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

using ll = long long; 

const int N = 3003; 
int cx[N][N], cy[N][N], n, m; 
string g[N]; 


int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m; 
	for (int i = 0; i < n; ++i) cin >> g[i]; 

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cx[i][j] = cy[i][j] = 0; 
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = m - 1; j >= 0; --j) {
			cx[i][j] += cx[i][j + 1]; 
			if (g[i][j] == 'O') cx[i][j]++; 
		}
	}
	for (int j = 0; j < m; ++j) {
		for (int i = n - 1; i >= 0; --i) {
			cy[i][j] += cy[i + 1][j]; 
			if (g[i][j] == 'I') cy[i][j]++; 
		}
	}
	ll ans = 0; 
	for (int i = 0; i < n; ++i) { 
		for (int j = 0; j < m; ++j) {
			if (g[i][j] == 'J') {
				ans += cx[i][j] * cy[i][j]; 
			}
		}
	}
	cout << ans << "\n";

	return 0; 
}	

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