제출 #234564

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
234564		nicolaalexandra	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	39 ms	4648 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
    cnt_left[0] = -1;
    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;
}

컴파일 시 표준 에러 (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: 12 / 12
• Subtask 3: 87 / 87