oj.uz

Submission #1045388

# Submission time Handle Problem Language Result Execution time Memory
1045388 2024-08-05T22:39:37 Z shezitt JJOOII 2 (JOI20_ho_t2) C++14
13 / 100
 2000 ms 5604 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;

#define int ll 
#define fore(a, b, c) for(int a=b; a<c; ++a)
#define vi vector<int>
#define pb push_back
#define ii pair<int,int>
#define F first 
#define S second 
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define dbg(x) cerr << #x << ": " << x << endl
#define raya cerr << "========================" << endl

const int N = 2e5+5;

int n, k;
string s;

int contJ[N], contO[N], contI[N];

int findj(int i){
    for(int j=i; j<n; ++j){
        int res = contJ[j] - (i == 0 ? 0 : contJ[i-1]);
        if(res == k) return j;
    }
    return -1;
}

int findl(int j){
    for(int l=j+1; l<n; ++l){
        int res = contO[l] - contO[j];
        if(res == k) return l;
    }
    return -1;
}

int findm(int l){
    for(int m=l+1; m<n; ++m){
        int res = contI[m] - contI[l];
        if(res == k) return m;
    }
    return -1;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;
    cin >> s;

    // contJ
    for(int i=0; i<n; ++i){

        contJ[i] += (s[i] == 'J');
        contO[i] += (s[i] == 'O');
        contI[i] += (s[i] == 'I');

        contJ[i+1] = contJ[i];
        contO[i+1] = contO[i];
        contI[i+1] = contI[i];
    }

    int ans = n;

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

        // then go to j
        int j = findj(i);
        if(j == -1) continue;
        // then go to l
        int l = findl(j);
        if(l == -1) continue;
        // then go to m
        int m = findm(l);
        if(m == -1) continue;

        int cur = j - i + 1 - k;
        cur += l - j - k;
        cur += m - l - k;
        ans = min(ans, cur);

    }

    // assert(ans > -1);
    cout << (ans == n ? -1 : ans) << endl;

}

Subtask #1
1.0 / 1.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 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.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 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 512 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 2 ms 348 KB Output is correct

Subtask #3
0 / 87.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 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 512 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 2 ms 348 KB Output is correct
36 Correct 3 ms 5096 KB Output is correct
37 Correct 3 ms 5312 KB Output is correct
38 Correct 4 ms 5604 KB Output is correct
39 Correct 920 ms 5352 KB Output is correct
40 Execution timed out 2017 ms 5348 KB Time limit exceeded
41 Halted 0 ms 0 KB -