oj.uz

Submission #144815

# Submission time Handle Problem Language Result Execution time Memory
144815 2019-08-17T20:42:03 Z brcode Rabbit Carrot (LMIO19_triusis) C++14
0 / 100
 6 ms 632 KB 
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const long long MAXN = 2e5+5;
long long arr[MAXN];
long long d[MAXN];
int main(){
    long long n,k;
    cin>>n>>k;
    const long long INF = 1e18;
    vector<long long> d(n+2, -INF);
    d[n+1] = 0;
    
    for(long long i=1;i<=n;i++){
        cin>>arr[i];
        arr[i]-=(k*i);
        
    }
    for(long long i=1;i<=n;i++){
        long long j = upper_bound(d.begin(), d.end(), arr[i]) - d.begin();
        
        if(d[j-1]<=arr[i] && d[j]>arr[i]){
            d[j-1] = arr[i];
        }
       // cout<<j<<endl;
    }
    long long ans = 0;
    
    for(long long i=1;i<=n;i++){
        if(d[i]!=-1e18){
           ans = max(ans,n-i+1);
        }
    }
    cout<<n-ans<<endl;
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Incorrect 5 ms 504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Incorrect 5 ms 504 KB Output isn't correct
5 Halted 0 ms 0 KB -