oj.uz

Submission #58744

# Submission time Handle Problem Language Result Execution time Memory
58744 2018-07-19T06:24:12 Z leejseo None (JOI16_ho_t2) C++
100 / 100
 13 ms 6800 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 3 ms 600 KB Output is correct
4 Correct 3 ms 620 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 3 ms 636 KB Output is correct
7 Correct 2 ms 648 KB Output is correct
8 Correct 3 ms 652 KB Output is correct
9 Correct 2 ms 656 KB Output is correct
10 Correct 2 ms 656 KB Output is correct
11 Correct 3 ms 792 KB Output is correct
12 Correct 2 ms 792 KB Output is correct
13 Correct 3 ms 792 KB Output is correct
14 Correct 3 ms 792 KB Output is correct
15 Correct 3 ms 792 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 3 ms 600 KB Output is correct
4 Correct 3 ms 620 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 3 ms 636 KB Output is correct
7 Correct 2 ms 648 KB Output is correct
8 Correct 3 ms 652 KB Output is correct
9 Correct 2 ms 656 KB Output is correct
10 Correct 2 ms 656 KB Output is correct
11 Correct 3 ms 792 KB Output is correct
12 Correct 2 ms 792 KB Output is correct
13 Correct 3 ms 792 KB Output is correct
14 Correct 3 ms 792 KB Output is correct
15 Correct 3 ms 792 KB Output is correct
16 Correct 3 ms 848 KB Output is correct
17 Correct 3 ms 968 KB Output is correct
18 Correct 3 ms 968 KB Output is correct
19 Correct 3 ms 968 KB Output is correct
20 Correct 2 ms 968 KB Output is correct
21 Correct 3 ms 968 KB Output is correct
22 Correct 2 ms 968 KB Output is correct
23 Correct 3 ms 968 KB Output is correct
24 Correct 4 ms 968 KB Output is correct
25 Correct 3 ms 968 KB Output is correct
26 Correct 3 ms 968 KB Output is correct
27 Correct 2 ms 968 KB Output is correct
28 Correct 4 ms 968 KB Output is correct
29 Correct 3 ms 968 KB Output is correct
30 Correct 3 ms 968 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 3 ms 600 KB Output is correct
4 Correct 3 ms 620 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 3 ms 636 KB Output is correct
7 Correct 2 ms 648 KB Output is correct
8 Correct 3 ms 652 KB Output is correct
9 Correct 2 ms 656 KB Output is correct
10 Correct 2 ms 656 KB Output is correct
11 Correct 3 ms 792 KB Output is correct
12 Correct 2 ms 792 KB Output is correct
13 Correct 3 ms 792 KB Output is correct
14 Correct 3 ms 792 KB Output is correct
15 Correct 3 ms 792 KB Output is correct
16 Correct 3 ms 848 KB Output is correct
17 Correct 3 ms 968 KB Output is correct
18 Correct 3 ms 968 KB Output is correct
19 Correct 3 ms 968 KB Output is correct
20 Correct 2 ms 968 KB Output is correct
21 Correct 3 ms 968 KB Output is correct
22 Correct 2 ms 968 KB Output is correct
23 Correct 3 ms 968 KB Output is correct
24 Correct 4 ms 968 KB Output is correct
25 Correct 3 ms 968 KB Output is correct
26 Correct 3 ms 968 KB Output is correct
27 Correct 2 ms 968 KB Output is correct
28 Correct 4 ms 968 KB Output is correct
29 Correct 3 ms 968 KB Output is correct
30 Correct 3 ms 968 KB Output is correct
31 Correct 9 ms 5316 KB Output is correct
32 Correct 10 ms 5416 KB Output is correct
33 Correct 9 ms 5532 KB Output is correct
34 Correct 9 ms 5648 KB Output is correct
35 Correct 9 ms 5788 KB Output is correct
36 Correct 13 ms 5884 KB Output is correct
37 Correct 9 ms 5984 KB Output is correct
38 Correct 10 ms 6100 KB Output is correct
39 Correct 10 ms 6200 KB Output is correct
40 Correct 7 ms 6300 KB Output is correct
41 Correct 9 ms 6400 KB Output is correct
42 Correct 10 ms 6500 KB Output is correct
43 Correct 12 ms 6608 KB Output is correct
44 Correct 9 ms 6704 KB Output is correct
45 Correct 10 ms 6800 KB Output is correct