Submission #709490

#	Time	Username	Problem	Language	Result	Execution time	Memory
709490		thanhnhanqn77	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	29 ms	6256 KiB

triusis

#include <bits/stdc++.h>
#define fu(i, a, b) for(int i = (a); i <= (b); i++)
#define fd(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long
using namespace std;
const int N = 2e5 + 5;
const int MAXA = 1e9 + 5;
const int INF = 1e9 + 5;

int n;
ll lim;
ll a[N];
ll dp[N];
vector<int> lis;


int LIS()
{
    int maxlen = 0;
    int sz = (int)lis.size();
    fu(i, 0, sz - 1)
    {
       int x = upper_bound(dp, dp + maxlen, lis[i]) - dp;
       if(x == maxlen) {
            dp[maxlen] = lis[i];
            maxlen++;
       }
       else {
            dp[x] = lis[i];
       }
    }
    return maxlen;

}

void solve()
{
    fu(i, 1, n)
    {
        if(i * lim >= a[i]) {
            lis.push_back((ll)i * lim - a[i]);
        }
    }
    cout << n - LIS();
}

void read()
{
    cin >> n >> lim;
    fu(i, 1, n) cin >> a[i];
    solve();

}

int main()
{
//    freopen("tester.inp","r",stdin);
//    freopen("tester.out","w",stdout);
    ios_base::sync_with_stdio(false);cin.tie(0);
    read();
}

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