Submission #58744

#	Time	Username	Problem	Language	Result	Execution time	Memory
58744		leejseo	스탬프 수집 (JOI16_ho_t2)	C++98	100 / 100	13 ms	6800 KiB

2016_ho_t2

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int MAXN = 100000;
int N, L[MAXN+1][3], R[MAXN+1][3], A[MAXN];
lld X[MAXN+1], Y[MAXN+1];
char s[MAXN+1];
lld S;

inline int conv(char c){
    if (c == 'J') return 0;
    if (c == 'O') return 1;
    return 2;
}

void input(){
    scanf("%d\n", &N);
    scanf("%s", s);
    for (int i=0; i<N; i++) A[i] = conv(s[i]);
}

void init(){
    for (int i=0; i<N; i++){
        L[i+1][0] = L[i][0];
        L[i+1][1] = L[i][1];
        L[i+1][2] = L[i][2];
        L[i+1][A[i]]++;
    }
    for (int i=N-1; i>=0; i--){
        R[i][0] = R[i+1][0];
        R[i][1] = R[i+1][1];
        R[i][2] = R[i+1][2];
        R[i][A[i]]++;
    }
    for (int i=0; i<N; i++){
        if (A[i] == 1){
            X[i] = L[i][0];
            Y[i] = R[i][2];
            S += L[i][0] * (lld) R[i][2];
        }
    }
    for (int i=1; i<=N; i++) X[i] += X[i-1];
    for (int i=N-1; i>=0; i--) Y[i] += Y[i+1];
}


lld solve(){
    lld ans = 0;
    for (int i=0; i<=N; i++){
        ans = max(ans, Y[i]);
        ans = max(ans, X[i]);
        ans = max(ans, L[i][0] * (lld)R[i][2]);
    }
    return ans;
}

int main(){
    input();
    init();
    printf("%lld\n", S+solve());
}

Compilation message (stderr)

2016_ho_t2.cpp: In function 'void input()':
2016_ho_t2.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d\n", &N);
     ~~~~~^~~~~~~~~~~~
2016_ho_t2.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s);
     ~~~~~^~~~~~~~~

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