Submission #896398

#	Time	Username	Problem	Language	Result	Execution time	Memory
896398		MongHwa	스탬프 수집 (JOI16_ho_t2)	C++17	100 / 100	5 ms	3160 KiB

2016_ho_t2

#include <iostream>
using namespace std;

#define ll long long

ll J[100005], O[100005], I[100005];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n; string s;
	cin >> n >> s;

	ll org = 0;
	for(int i = 0; i < n; i++)
	{
		J[i+1] = J[i];
		if(s[i] == 'J')
			J[i+1]++;
	}
	for(int i = 0; i < n; i++)
	{
		O[i+1] = O[i];
		if(s[i] == 'O')
			O[i+1] += J[i+1];
	}
	for(int i = 0; i < n; i++)
	{
		I[i+1] = I[i];
		if(s[i] == 'I')
			I[i+1] += O[i+1];
	}
	org = I[n];

	ll ans = org;
	for(int i = 1; i <= n; i++)
		ans = max(ans, org + O[i]);

	fill(O, O+n+1, 0);
	fill(I, I+n+1, 0);

	for(int i = n-1; i >= 0; i--)
	{
		I[i] = I[i+1];
		if(s[i] == 'I')
			I[i]++;
	}
	for(int i = n-1; i >= 0; i--)
	{
		O[i] = O[i+1];
		if(s[i] == 'O')
			O[i] += I[i];
	}

	for(int i = 0; i < n; i++)
		ans = max(ans, org + O[i]);

	fill(J, J+n+1, 0);
	fill(I, I+n+1, 0);

	for(int i = 0; i < n; i++)
	{
		J[i+1] = J[i], I[i+1] = I[i];
		if(s[i] == 'J')
			J[i+1]++;
		else if(s[i] == 'I')
			I[i+1]++;
	}

	for(int i = 1; i < n; i++)
		ans = max(ans, org + J[i]*(I[n]-I[i]));

	cout << ans << '\n';
}

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