제출 #775466

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
775466		hgmhc	스탬프 수집 (JOI16_ho_t2)	C++17	100 / 100	4 ms	3644 KiB

2016_ho_t2

#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x),end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define dbg(...) fprintf(stdout,__VA_ARGS__)
#define fi first
#define se second
using namespace std; using ll = long long; using ii = pair<int,int>;

const int N = 1e5+3;
int n;
char s[N];
ll ans, diff;
ll cJ[N], cI[N];
ll cJO[N], cOI[N];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    // 지문이 너무 난해하다..
    // 조합.. 든든하군
    cin >> n >> &s[1];
    rep(i,1,n) cJ[i] = cJ[i-1]+(s[i]=='J');
    per(i,1,n) cI[i] = cI[i+1]+(s[i]=='I');
    rep(i,1,n) if (s[i]=='O') ans += cJ[i-1]*cI[i+1];
    
    rep(i,1,n) {
        cJO[i] = cJO[i-1];
        if (s[i]=='O') cJO[i] += cJ[i-1];
    }
    
    per(i,1,n) {
        cOI[i] = cOI[i+1];
        if (s[i]=='O') cOI[i] += cI[i+1];
    }
    
    rep(i,0,n) {
        // between i and i+1
        // select 'J'
        Mup(diff, cOI[i+1]);
        // select 'O'
        Mup(diff, cJ[i]*cI[i+1]);
        // select 'I'
        Mup(diff, cJO[i]);
    }
    
    cout << ans+diff;
}

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