제출 #1323972

#제출 시각아이디문제언어결과실행 시간메모리
1323972ppmn_6스탬프 수집 (JOI16_ho_t2)C++20
100 / 100
4 ms5172 KiB
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// https://codeforces.com/blog/entry/79148
class Timer: chrono::high_resolution_clock {
    const time_point start_time;
public:
    Timer(): start_time(now()) {}
    rep elapsed_time() const {
		return chrono::duration_cast<chrono::milliseconds>(now() - start_time).count();
	}
} timer;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	string s;
	cin >> n >> s;
	s = "~" + s;
	vector<ll> cntj(n + 2), cnto(n + 2), cnti(n + 2), cntjr(n + 2), cntor(n + 2), cntir(n + 2);
	for (int i = 1; i <= n; i++) {
		cntj[i] = cntj[i - 1];
		cnto[i] = cnto[i - 1];
		cnti[i] = cnti[i - 1];
		if (s[i] == 'J') {
			cntj[i]++;
		}
		if (s[i] == 'O') {
			cnto[i] += cntj[i - 1];
		}
		if (s[i] == 'I') {
			cnti[i] += cnto[i - 1];
		}
	}
	for (int i = n; i >= 1; i--) {
		cntjr[i] = cntjr[i + 1];
		cntor[i] = cntor[i + 1];
		cntir[i] = cntir[i + 1];
		if (s[i] == 'J') {
			cntjr[i] += cntor[i + 1];
		}
		if (s[i] == 'O') {
			cntor[i] += cntir[i + 1];
		}
		if (s[i] == 'I') {
			cntir[i]++;
		}
	}
	ll ans = 0;
	for (int i = 1; i <= n + 1; i++) {
		ans = max({ans, cntor[i], cntj[i - 1] * cntir[i], cnto[i - 1]});
	}
	cout << ans + cnti[n];
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...