Submission #597686

#	Time	Username	Problem	Language	Result	Execution time	Memory
597686		Deepesson	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	209 ms	11248 KiB

prison

#include <bits/stdc++.h>
typedef std::pair<int,int> pii;

int main()
{
    int N,T,K;
    std::cin>>N>>K>>T;
    int array[N];for(auto&x:array)std::cin>>x;
    ///Tarefa: Achar para cada cara o PRIMEIRO x valido
    int dp[N]={};
    ///Quero minimizar o custo
    std::deque<pii> stack;
    for(int i=0;i!=N;++i){
        int custo = array[i]-i;
        while(stack.size()&&stack.front().first>custo){
            stack.pop_front();
        }
        stack.push_front({custo,i});
        ///O valor tem que ser menor ou igual ao desejo
        int desejo = T-i;
        int l=0,r=stack.size()-1;
        while(l<r){
            int m = (l+r)/2;
            if(stack[m].first<=desejo){
                r=m;
            }else l=m+1;
        }
        if(stack[l].first<=desejo){
          //  printf("Liga %d %d\n",i,stack[l].second);
            ++dp[stack[l].second];
        }
    }
    std::vector<int> vec;
    for(int i=0;i!=N;++i)vec.push_back(dp[i]);
    std::sort(vec.begin(),vec.end(),std::greater<int>());
    int sum=0;
    for(int i=0;i!=K;++i)sum+=std::max(0,vec[i]-1);
    std::cout<<(N-sum)<<"\n";
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20