Submission #597692

#	Time	Username	Problem	Language	Result	Execution time	Memory
597692		Deepesson	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	214 ms	6316 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();
        }

        ///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.size()&&array[i]>T){
            if(stack[l].first<=desejo){
              //  printf("Liga %d %d\n",i,stack[l].second);
                ++dp[stack[l].second];
            }
        }else stack.push_front({custo,i});
    }
    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+=vec[i];
    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