oj.uz

Submission #947618

# Submission time Handle Problem Language Result Execution time Memory
947618 2024-03-16T16:26:13 Z LOLOLO JOIOJI (JOI14_joioji) C++17
100 / 100
 20 ms 14628 KB 
#include <bits/stdc++.h>
typedef long long ll;

#define           f    first
#define           s    second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)

using namespace std;
const int N = 4e5 + 100;
const int M = 2e5;
int p[N], pr[N];
vector <int> pos[N];

int solve() {
    int n;
    cin >> n;

    string s;
    cin >> s;
    s = '0' + s;

    p[0] = M;
    pos[M].pb(0);

    for (int i = 1; i <= n; i++) {
        if (s[i] == 'J') {
            p[i]++;
        }

        if (s[i] == 'O') {
            p[i]--;
        }

        if (s[i] == 'I') {
            pr[i]++;
        }

        pr[i] += pr[i - 1];
        p[i] += p[i - 1];
        pos[p[i]].pb(i);
    }

    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (pos[i].empty())
            continue;

        map <int, int> mp;
        for (auto x : pos[i]) {
            int cur = x - pr[x] * 3;
            if (mp.find(cur) != mp.end()) {
                ans = max(ans, x - mp[cur]);
            } else {
                mp[cur] = x;
            }
        }
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    //cin >> t;

    while (t--) {
        cout << solve() << '\n';
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 4 ms 12888 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 5 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 3 ms 12936 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 4 ms 12892 KB Output is correct
10 Correct 4 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 4 ms 12940 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 4 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 13016 KB Output is correct
10 Correct 4 ms 12892 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12892 KB Output is correct
2 Correct 5 ms 13148 KB Output is correct
3 Correct 7 ms 13148 KB Output is correct
4 Correct 10 ms 13652 KB Output is correct
5 Correct 14 ms 13964 KB Output is correct
6 Correct 19 ms 14360 KB Output is correct
7 Correct 19 ms 14372 KB Output is correct
8 Correct 20 ms 14628 KB Output is correct
9 Correct 19 ms 14368 KB Output is correct
10 Correct 19 ms 14404 KB Output is correct
11 Correct 12 ms 14592 KB Output is correct
12 Correct 19 ms 14388 KB Output is correct
13 Correct 9 ms 14376 KB Output is correct
14 Correct 12 ms 14444 KB Output is correct
15 Correct 9 ms 14368 KB Output is correct