oj.uz

Submission #234563

# Submission time Handle Problem Language Result Execution time Memory
234563 2020-05-24T14:18:10 Z nicolaalexandra JJOOII 2 (JOI20_ho_t2) C++14
1 / 100
 6 ms 384 KB 
#include <bits/stdc++.h>
#define DIM 200010
using namespace std;
int sp_j[DIM],sp_i[DIM],sp_o[DIM],cnt_left[DIM],cnt_right[DIM];
char v[DIM];
int n,k,i;

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>k>>v+1;

    for (i=1;i<=n;i++){
        sp_j[i] = sp_j[i-1] + (v[i] == 'J');
        sp_o[i] = sp_o[i-1] + (v[i] == 'O');
        sp_i[i] = sp_i[i-1] + (v[i] == 'I');
    }

    /// cnt_left[i] - nr minim de caractere pe care trebuie sa le sterg a.i sa am k de J
    for (i=1;i<=n;i++){

        int st = 1, dr = i, sol = -1;
        while (st <= dr){
            int mid = (st+dr)>>1;
            if (sp_j[i] - sp_j[mid-1] >= k){
                sol = mid;
                st = mid+1;
            } else dr = mid-1;
        }

        if (sol == -1)
            cnt_left[i] = -1;
        else cnt_left[i] = i - sol + 1 - k;
    }

    /// cnt_right[i] - sa am k de I de la poz i in dreapta

    for (i=1;i<=n;i++){
        int st = i, dr = n, sol = -1;
        while (st <= dr){
            int mid = (st+dr)>>1;
            if (sp_i[mid] - sp_i[i-1] >= k){
                sol = mid;
                dr = mid-1;
            } else st = mid+1;
        }

        if (sol == -1)
            cnt_right[i] = -1;
        else cnt_right[i] = sol - i + 1 - k;
    }

    int ans = n+1;
    for (i=1;i<=n;i++){
        if (cnt_right[i] == -1)
            continue;
        int st = 1, dr = i-1, sol = -1;
        while (st <= dr){
            int mid = (st+dr)>>1;
            if (sp_o[i-1] - sp_o[mid-1] >= k){
                sol = mid;
                st = mid+1;
            } else dr = mid-1;
        }

        if (sol != -1 && cnt_left[sol-1] != -1)
            ans = min (ans, cnt_right[i] + cnt_left[sol-1] + i-1 - sol + 1 - k);
    }

    if (ans == n+1)
        cout<<-1;
    else cout<<ans;

    return 0;
}

Compilation message

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:13:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     cin>>n>>k>>v+1;
                ~^~

Subtask #1
1.0 / 1.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Incorrect 5 ms 384 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Incorrect 5 ms 384 KB Output isn't correct
22 Halted 0 ms 0 KB -