fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. bool check(int N,int pos){return (bool)(N&(1LL<<pos));}
  5. unsigned int SET(int N,int pos){return (N|(1<<pos));}
  6. long long int dp[50010],n,k,arr[50010];
  7.  
  8. long long int go(){
  9.     if(n==0) return 0;
  10.     if(n==1) return 1;
  11.     if(n==2){
  12.         if(arr[0]>arr[1] && k){
  13.             return 2;
  14.         }
  15.         else if(arr[0]>arr[1] && !k){
  16.             return 1;
  17.         }
  18.         else if(arr[0]<arr[1]){
  19.             return 2;
  20.         }
  21.         else if(arr[0]== arr[1]) return 2;
  22.     }
  23.     dp[0]=1;
  24.     if(k && arr[0]>arr[1]) {dp[1]=2;k--;}
  25.     if(arr[0]>arr[1] && !k) dp[1]=1;
  26.     if(arr[0]<arr[1]) dp[1]=2;
  27.     if(arr[0]==arr[1]) dp[1]=2;
  28.     for(int i=2;i<n;i++){
  29.         if(arr[i-1]>arr[i] && k) {dp[i]=dp[i-1]+1;k--;}
  30.         else if(arr[i-1]>arr[i] && !k) dp[i]=dp[i-1];
  31.         else if(arr[i-1]<arr[i]) dp[i]=dp[i-1]+1;
  32.     }
  33.     return dp[n-1];
  34.  
  35. }
  36.  
  37. int main()
  38. {
  39.  
  40.         memset(dp,-1,sizeof(dp));
  41.  
  42.         cin>>n>>k;
  43.  
  44.         for(int i=0;i<n;i++){
  45.             cin>>arr[i];
  46.         }
  47.  
  48.         int tot = 0;
  49.         for (int i = 1; i < n; i++) {
  50.             tot += (int)(arr[i] < arr[i - 1]);
  51.         }
  52.         if (tot <= k) {
  53.             printf("%d\n", n);
  54.             return 0;
  55.         }
  56.         cout<<go()<<endl;
  57.  
  58. }
  59.  
Success #stdin #stdout 0.01s 5500KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/CeldIV
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!