Submission #234563

#	Time	Username	Problem	Language	Result	Execution time	Memory
234563		nicolaalexandra	JJOOII 2 (JOI20_ho_t2)	C++14	1 / 100	6 ms	384 KiB

ho_t2

#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 (stderr)

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 / 1
• Subtask 2: 0 / 12
• Subtask 3: 0 / 87