oj.uz

답안 #597686

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
597686 2022-07-16T14:44:02 Z Deepesson The short shank; Redemption (BOI21_prison) C++17
0 / 100
 209 ms 11248 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 300 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 304 KB Output is correct
2 Incorrect 209 ms 11248 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 300 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 33 ms 2224 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 300 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 300 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -