Submission #732820

#	Time	Username	Problem	Language	Result	Execution time	Memory
732820		flappybird	스탬프 수집 (JOI16_ho_t2)	C++17	100 / 100	6 ms	4184 KiB

2016_ho_t2

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
int arr[MAX];
ll pj[MAX];
ll pjo[MAX];
ll si[MAX];
ll soi[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N;
	cin >> N;
	string s;
	cin >> s;
	int i;
	for (i = 1; i <= N; i++) if (s[i - 1] != 'J') arr[i] = s[i - 1] == 'O' ? 1 : 2;
	for (i = 1; i <= N; i++) {
		if (!arr[i]) pj[i] = 1;
		pj[i] += pj[i - 1];
		if (arr[i] == 1) pjo[i] += pj[i - 1];
		pjo[i] += pjo[i - 1];
	}
	for (i = N; i >= 1; i--) {
		if (arr[i] == 2) si[i] = 1;
		si[i] += si[i + 1];
		if (arr[i] == 1) soi[i] += si[i + 1];
		soi[i] += soi[i + 1];
	}
	ll ans = 0;
	for (i = 1; i <= N; i++) if (arr[i] == 1) ans += pj[i] * si[i];
	ll mx = 0;
	for (i = 1; i < N; i++) mx = max(mx, pj[i] * si[i + 1]);
	mx = max(mx, soi[1]);
	mx = max(mx, pjo[N]);
	cout << ans + mx << ln;
}

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