Submission #703217

#	Time	Username	Problem	Language	Result	Execution time	Memory
703217		LonlyR	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	29 ms	5376 KiB

triusis

#include<bits/stdc++.h>
#define int long long

/**
    the least number of changes = the most number of heights that do not change
    LIS:   i1, i2, i3, ...., ik
        a[ij]<= ij*M
        a[ij+1] <= a[ij] + (ij+1-ij)*M
    <=> M*ij - a[ij] >=0
        M*ij - a[ij] <= M*(ij+1) - a[ij+1]
    <=> make b[i] = M*i - a[i]
    then ans = n - length of the longest non-decreasing subsequence of b
**/

using namespace std;
const int maxn=2e5+5,inf=1e18;
int n,m,ans;
int b[maxn],dp[maxn];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for (int i=1,x;i<=n;i++) cin>>x,b[i]=m*i-x,dp[i]=inf;
    for (int i=1;i<=n;i++)
    {
        if (b[i]<0) continue;
        int pos=upper_bound(dp+1,dp+n+1,b[i])-dp;
        ans=max(ans,pos);
        dp[pos]=b[i];
    }
    cout<<n-ans;
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37