oj.uz

Submission #579609

# Submission time Handle Problem Language Result Execution time Memory
579609 2022-06-19T13:26:19 Z LOLOLO Rabbit Carrot (LMIO19_triusis) C++17
0 / 100
 1000 ms 340 KB 
#include <bits/stdc++.h>
#define ll long long 
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
vector<ll>fen;
ll sz;
void upd(ll i,ll x){
    while(i<sz){
        fen[i]=min(fen[i],x);
        i+=i&(-i);
    }
}

int cal(int i){
    ll v=1e9;
    while(i<sz){
        v=min(v,fen[i]);
        i+=i&(-i);
    }
    return v;
}

int main(){
    int n,m;
    cin>>n>>m;
    vector<int>A;
    vector<int>h(n+1);
    A.push_back(0);
    A.push_back(-(n+1)*m);
    for(int i=1;i<=n;i++){
        cin>>h[i];
        A.push_back(h[i]-i*m);
    }
    h.push_back(0);

    sort(A.begin(),A.end());
    vector<ll>dp(n+10000+1,1e9);
    fen=dp;
    sz=n+10000+1;
    fen=dp;
    dp[0]=0;
    upd(upper_bound(A.begin(),A.end(),0)-A.begin(),0);
    for(int i=1;i<=n+1;i++){
        ll pos=lower_bound(A.begin(),A.end(),h[i])-A.begin();
        ll val=cal(pos);
        dp[i]=val+i;
        upd(pos,dp[i]-i-1);
    }
    cout<<dp[n+1]<<endl;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -