제출 #1338831

#제출 시각아이디문제언어결과실행 시간메모리
1338831Nipphitch스탬프 수집 (JOI16_ho_t2)C++20
100 / 100
4 ms4420 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int N=1e5+5;

int n,dplj[N],dpljo[N],dpljoi[N],dpri[N],dproi[N],mx;
char c[N];

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++) cin >> c[i];
    for(int i=1;i<=n;i++){
        dplj[i]=dplj[i-1];
        dpljo[i]=dpljo[i-1];
        dpljoi[i]=dpljoi[i-1];
        if(c[i]=='J') dplj[i]++;
        else if(c[i]=='O') dpljo[i]+=dplj[i-1];
        else dpljoi[i]+=dpljo[i-1];
    }
    for(int i=n;i>=1;i--){
        dpri[i]=dpri[i+1];
        dproi[i]=dproi[i+1];
        if(c[i]=='I') dpri[i]++;
        else if(c[i]=='O') dproi[i]+=dpri[i+1];
    }
    mx=max(dpljo[n],dproi[1]);
    for(int i=0;i<=n;i++) mx=max(mx,dplj[i]*dpri[i+1]);
    cout << dpljoi[n]+mx;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...