Submission #1206000

#TimeUsernameProblemLanguageResultExecution timeMemory
1206000agrim_09스탬프 수집 (JOI16_ho_t2)C++20
100 / 100
4 ms4424 KiB
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define endl '\n';
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define py cout << "YES" << endl;
#define pn cout << "NO" << endl;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define int long long
typedef long long ll;
typedef unsigned long long ull;
const ll inf = 1e18;
const ll mod = 1e9+7;


// #ifndef ONLINE_JUDGE
// #include "algo/Standard_Stuff/debug.cpp"
// #else
// #define debug(...) 42
// #endif

// void judge(){
//     srand(time(NULL));
//     #ifndef ONLINE_JUDGE
//     freopen("1.txt","r",stdin);
//     freopen("2.txt","w",stdout);
//     #endif
// }

// Look for edge cases!!!
signed main(){
    fastio; //judge();
    int n; cin >> n;
    string s; cin >> s;
    vector<int>pref_count_j(n+1,0), pref_count_jo(n+1,0), pref_count_joi(n+1,0);
    for(int i = 1;i<=n;i++){
        pref_count_j[i] = pref_count_j[i-1] + (s[i-1]=='J');
        pref_count_jo[i] = pref_count_jo[i - 1] + (s[i-1] == 'O') * pref_count_j[i - 1];
        pref_count_joi[i] = pref_count_joi[i-1] + (s[i-1]=='I')*pref_count_jo[i-1];
    }
    pref_count_j.erase(pref_count_j.begin());
    pref_count_jo.erase(pref_count_jo.begin());
    pref_count_joi.erase(pref_count_joi.begin());
    // pref_count[i] gives from [0,i]

    vector<int>suff_count_i(n+1,0), suff_count_oi(n+1,0);
    for(int i = n-1;i>=0;i--){
        suff_count_i[i] = suff_count_i[i+1] + (s[i]=='I');
        suff_count_oi[i] = suff_count_oi[i+1] + (s[i]=='O')*suff_count_i[i+1];
    }
    // suff_count[i] gives from [i,n-1]

    int ans = pref_count_joi[n-1] + max(suff_count_oi[0],pref_count_jo[n-1]); // Extreme cases

    for(int i = 0;i<n-1;i++){
        // between i and i+1;
        int curr = pref_count_joi[n-1];
        // if I insert J
        int tmp = curr;
        tmp += suff_count_oi[i+1];
        ans = max(ans,tmp);
        // if I insert O
        tmp = curr;
        tmp += pref_count_j[i]*suff_count_i[i+1];
        ans = max(ans,tmp);
        // if I insert I
        tmp = curr;
        tmp += pref_count_jo[i];
        ans = max(ans,tmp);
    }
    cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...