oj.uz

Submission #888160

# Submission time Handle Problem Language Result Execution time Memory
888160 2023-12-16T09:03:52 Z Unforgettablepl JJOOII 2 (JOI20_ho_t2) C++17
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int INF = INT64_MAX;

int prefix[200001][3];

int32_t main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,k;
    cin >> n >> k;
    for(int i=1;i<=n;i++){
        char a;cin>>a;
        prefix[i][0]=prefix[i-1][0];
        prefix[i][1]=prefix[i-1][1];
        prefix[i][2]=prefix[i-1][2];
        if(a=='J')prefix[i][0]++;
        else if(a=='O')prefix[i][1]++;
        else prefix[i][2]++;
    }
    int ans = INF;
    for(int l=1;l<=n;l++){
        if(prefix[l][0]-prefix[l-1][0]==0)continue;
        if(prefix[n][0]-prefix[l-1][0]<k)break;
        int mid1 = l;
        for(int jump=2e5;jump;jump/=2){
            if(mid1+jump>n)continue;
            while(prefix[mid1+jump][0]-prefix[l-1][0]<k)mid1+=jump;
        }
        mid1++;
        if(prefix[n][1]-prefix[mid1-1][1]<k)break;
        int mid2 = mid1;
        for(int jump=2e5;jump;jump/=2){
            if(mid2+jump>n)continue;
            while(prefix[mid2+jump][1]-prefix[mid1-1][1]<k)mid2+=jump;
        }
        mid2++;
        if(prefix[n][2]-prefix[mid2-1][2]<k)break;
        int r = mid2;
        for(int jump=2e5;jump;jump/=2){
            if(r+jump>n)continue;
            while(prefix[r+jump][2]-prefix[mid2-1][2]<k)r+=jump;
        }
        r++;
        ans = min(ans,r-l);
    }
    if(ans==INF)cout << "-1\n";
    else cout << ans+1-3*k << '\n';
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -