oj.uz

Submission #1095204

# Submission time Handle Problem Language Result Execution time Memory
1095204 2024-10-01T14:52:44 Z phong None (JOI16_ho_t2) C++17
100 / 100
 6 ms 8596 KB 
#include<bits/stdc++.h>
#define ll long long
#define int long long
const int nmax = 1e5 + 5, N = 2e6;
const ll oo = 1e12 + 5, base = 3001;
const int lg = 17,mod = 998244353;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n;
string s;
int pre[nmax][5], suf[nmax][5];

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("FRIENDS.inp", "r", stdin);
//    freopen("FRIENDS.out", "w", stdout);
    cin >> n;
    cin >> s;
    s = ' ' + s;
    int cur = 0;
    for(int i = 1; i <= n; ++i){
        pre[i][0] = pre[i - 1][0] + (s[i] == 'J');
        pre[i][1] = pre[i - 1][1] + (s[i] == 'O');
        pre[i][2] = pre[i - 1][2] + (s[i] == 'I');
        pre[i][3] = pre[i - 1][3] + (s[i] == 'O') * pre[i - 1][0];
        pre[i][4] = pre[i - 1][4] + (s[i] == 'I') * pre[i - 1][1];
        if(s[i] == 'I') cur += pre[i - 1][3];
    }
    for(int i = n; i >= 1; --i){
        suf[i][0] = suf[i + 1][0] + (s[i] == 'J');
        suf[i][1] = suf[i + 1][1] + (s[i] == 'O');
        suf[i][2] = suf[i + 1][2] + (s[i] == 'I');
        suf[i][3] = suf[i + 1][3] + (s[i] == 'J') * suf[i + 1][1];
        suf[i][4] = suf[i + 1][4] + (s[i] == 'O') * suf[i + 1][2];
    }
    int ans = 0;
    for(int i = 0; i <= n; ++i){
        ans = max(ans, suf[i + 1][4]);
        ans = max(ans, pre[i][0] * suf[i + 1][2]);
        ans = max(ans, pre[i][3]);
    }
    cout << ans + cur;
}
/*
16 4 12

*/

Compilation message

2016_ho_t2.cpp:18:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   18 | main(){
      | ^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 472 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 472 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 0 ms 604 KB Output is correct
18 Correct 0 ms 600 KB Output is correct
19 Correct 0 ms 604 KB Output is correct
20 Correct 0 ms 604 KB Output is correct
21 Correct 0 ms 600 KB Output is correct
22 Correct 0 ms 600 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 0 ms 604 KB Output is correct
25 Correct 0 ms 604 KB Output is correct
26 Correct 0 ms 604 KB Output is correct
27 Correct 0 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 0 ms 604 KB Output is correct
30 Correct 0 ms 600 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 472 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 0 ms 604 KB Output is correct
18 Correct 0 ms 600 KB Output is correct
19 Correct 0 ms 604 KB Output is correct
20 Correct 0 ms 604 KB Output is correct
21 Correct 0 ms 600 KB Output is correct
22 Correct 0 ms 600 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 0 ms 604 KB Output is correct
25 Correct 0 ms 604 KB Output is correct
26 Correct 0 ms 604 KB Output is correct
27 Correct 0 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 0 ms 604 KB Output is correct
30 Correct 0 ms 600 KB Output is correct
31 Correct 4 ms 8276 KB Output is correct
32 Correct 4 ms 8532 KB Output is correct
33 Correct 4 ms 8536 KB Output is correct
34 Correct 4 ms 8536 KB Output is correct
35 Correct 4 ms 8520 KB Output is correct
36 Correct 4 ms 8408 KB Output is correct
37 Correct 6 ms 8536 KB Output is correct
38 Correct 4 ms 8536 KB Output is correct
39 Correct 5 ms 8536 KB Output is correct
40 Correct 4 ms 8596 KB Output is correct
41 Correct 5 ms 8536 KB Output is correct
42 Correct 4 ms 8520 KB Output is correct
43 Correct 4 ms 8536 KB Output is correct
44 Correct 4 ms 8536 KB Output is correct
45 Correct 4 ms 8408 KB Output is correct