Submission #166936

#	Time	Username	Problem	Language	Result	Execution time	Memory
166936		johutha	Bitaro the Brave (JOI19_ho_t1)	C++17	100 / 100	879 ms	212888 KiB

joi2019_ho_t1

#include <vector>
#include <iostream>

#define int int64_t

using namespace std;

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int h, w;
	cin >> h >> w;

	vector<vector<int>> pref_o(h, vector<int>(w + 1));
	vector<vector<int>> pref_i(w, vector<int>(h + 1));

	vector<pair<int,int>> js;

	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			pref_o[i][j + 1] = pref_o[i][j];
			pref_i[j][i + 1] = pref_i[j][i];
			char c;
			cin >> c;

			if (c == 'J') js.push_back({i, j});
			else if (c == 'I') pref_i[j][i + 1]++;
			else if (c == 'O') pref_o[i][j + 1]++;
		}
	}

	int ans = 0;

	for (auto p : js)
	{
		ans += (pref_i[p.second][h] - pref_i[p.second][p.first])*(pref_o[p.first][w] - pref_o[p.first][p.second]);
	}

	cout << ans << "\n";
}

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