Submission #896398

#TimeUsernameProblemLanguageResultExecution timeMemory
896398MongHwa스탬프 수집 (JOI16_ho_t2)C++17
100 / 100
5 ms3160 KiB
#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';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...