제출 #1261434

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1261434		one_unknown	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	24 ms	5052 KiB

triusis

#include <bits/stdc++.h>
using namespace std;

#define int long long
using vi = vector<int>;
using vpii = vector<pair<int,int>>;
#define MOD 1000000007
#define all(arr) arr.begin(), arr.end()
#define take(arr) for(auto &x : arr) cin >> x;
#define print(arr) for(auto &x : arr) cout << x << " "; cout << "\n";
#define out(val) cout<<((val == 1) ? "YES" : "NO")<<endl;

void solve() {
    int n,m; cin>>n>>m;
    vector<int> arr(n+1);

    vector<int> a;
    for(int i = 1; i<=n; ++i){
        cin>>arr[i];
        if(arr[i] <= (i * m)){
            arr[i] -= ((i) * m); 
            a.push_back(arr[i]);
        }

    }

    reverse(all(a));
    int k = a.size();
    const int inf = 1e18;
    vector<int> dp(k+1, inf);
    dp[0] = -inf;

    for(int i = 1; i<=k; ++i){
        int l = upper_bound(all(dp), a[i-1]) - dp.begin();
        if(dp[l-1] <= a[i-1] and dp[l] > a[i-1]){
            dp[l] = a[i-1];
        }
    }
    int mx = 0;
    for(int i = 1; i<=k; ++i){
        if(dp[i] != inf){
            mx = i;
        }
    }
    cout<<n - mx<<endl;


}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int t = 1;
    while (t--) {
        solve();
    }

    return 0;
}

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