Submission #982521

#	Time	Username	Problem	Language	Result	Execution time	Memory
982521		Rohak	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	31 ms	5584 KiB

triusis

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

#define UNSYNC ios::sync_with_stdio(false); cin.tie(nullptr);
#define all(x) x.begin(), x.end()
#define rep(i, ini, x) for (int i = ini; i < x; ++i)
#define per(i, fin, x) for (int i = fin; i >= x; --i)

const int MOD = 1e9 + 7;
int main()
{
    UNSYNC
    int N, M; cin >> N >> M;
    vector<int> A (N); rep(i, 0, N) cin >> A[i];
    vector<int> F;
    rep(i, 0, N){
        if (M * (i + 1) >= A[i]){
            F.push_back(M * (i + 1) - A[i]);
        }
    }
    int S = F.size();
    vector<i64> dp (S + 1, MOD); dp[0] = -MOD;
        
    rep(i, 0, S){
        i64 l = upper_bound(all(dp), F[i]) - dp.begin();
        dp[l] = F[i];
    }
    i64 ans = 0;
    rep(i, 0, S + 1){
        if (dp[i] < MOD) ans = i;
    }
    cout << N - ans << '\n';
    return 0;
}

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