Submission #1206000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206000		agrim_09	스탬프 수집 (JOI16_ho_t2)	C++20	100 / 100	4 ms	4424 KiB

2016_ho_t2

// #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;
}

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