Submission #923924

#	Time	Username	Problem	Language	Result	Execution time	Memory
923924		yeediot	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	12 ms	3376 KiB

ho_t2

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define pb push_back
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    setio();
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    s=' '+s;
    vector<vector<int>>pos(3);
    for(int i=1;i<=n;i++){
        if(s[i]=='J')pos[0].pb(200000-i);
        else if(s[i]=='O')pos[1].pb(i);
        else if(s[i]=='I')pos[2].pb(i);
    }
    reverse(all(pos[0]));
    int ans=8e18;
    //for(auto i:pos[0])cout<<i<<' ';
    //cout<<'\n';
    for(int i=0;i+k<=sz(pos[1]);i++){
        int l=pos[1][i];
        int r=pos[1][i+k-1];
        int temp=r-l+1-k;
        l=200000-l;
        //cout<<temp<<' ';
        int x=lower_bound(all(pos[0]),l)-pos[0].begin();
        if(x+k>sz(pos[0]))continue;
        int y=lower_bound(all(pos[2]),r)-pos[2].begin();
        if(y+k>sz(pos[2]))continue;
        //cout<<pos[0][x+k-1]<<' '<<l<<' ';
        temp+=pos[0][x+k-1]-l-k+pos[2][y+k-1]-r-k;
        ans=min(ans,temp);
    }
    if(ans==8e18){
        cout<<-1<<'\n';
    }
    else{
        cout<<ans<<'\n';
    }
}

• Subtask 1: 1 / 1
• Subtask 2: 12 / 12
• Subtask 3: 87 / 87