Submission #579609

#	Time	Username	Problem	Language	Result	Execution time	Memory
579609		LOLOLO	Rabbit Carrot (LMIO19_triusis)	C++17	0 / 100	1087 ms	340 KiB

triusis

#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
• Subtask 2: 0 / 21
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37