Submission #1095204

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

2016_ho_t2

#include<bits/stdc++.h>
#define ll long long
#define int long long
const int nmax = 1e5 + 5, N = 2e6;
const ll oo = 1e12 + 5, base = 3001;
const int lg = 17,mod = 998244353;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n;
string s;
int pre[nmax][5], suf[nmax][5];

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("FRIENDS.inp", "r", stdin);
//    freopen("FRIENDS.out", "w", stdout);
    cin >> n;
    cin >> s;
    s = ' ' + s;
    int cur = 0;
    for(int i = 1; i <= n; ++i){
        pre[i][0] = pre[i - 1][0] + (s[i] == 'J');
        pre[i][1] = pre[i - 1][1] + (s[i] == 'O');
        pre[i][2] = pre[i - 1][2] + (s[i] == 'I');
        pre[i][3] = pre[i - 1][3] + (s[i] == 'O') * pre[i - 1][0];
        pre[i][4] = pre[i - 1][4] + (s[i] == 'I') * pre[i - 1][1];
        if(s[i] == 'I') cur += pre[i - 1][3];
    }
    for(int i = n; i >= 1; --i){
        suf[i][0] = suf[i + 1][0] + (s[i] == 'J');
        suf[i][1] = suf[i + 1][1] + (s[i] == 'O');
        suf[i][2] = suf[i + 1][2] + (s[i] == 'I');
        suf[i][3] = suf[i + 1][3] + (s[i] == 'J') * suf[i + 1][1];
        suf[i][4] = suf[i + 1][4] + (s[i] == 'O') * suf[i + 1][2];
    }
    int ans = 0;
    for(int i = 0; i <= n; ++i){
        ans = max(ans, suf[i + 1][4]);
        ans = max(ans, pre[i][0] * suf[i + 1][2]);
        ans = max(ans, pre[i][3]);
    }
    cout << ans + cur;
}
/*
16 4 12

*/

Compilation message (stderr)

2016_ho_t2.cpp:18:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   18 | main(){
      | ^~~~

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