제출 #1361804

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1361804		khba	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	16 ms	6476 KiB

triusis

// author: khba

#include "bits/stdc++.h"
using namespace std;
#define int long long

const int inf = (int)1e18;

#ifdef khba
#include "C:\Users\Asus\Desktop\khba\debug.h"
#else
#define print(...) 42
#endif

int32_t main() {
#ifdef khba
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, M, add = 0;
    cin >> n >> M;
    vector<int> a(n);
    for (int& i : a) cin >> i;
    vector <int> b;
    for (int i = 0; i < a.size(); ++i) {
        a[i] -= (i + 1) * M, a[i] = -a[i];
        if (a[i] < 0) add += 1;
        else b.push_back(a[i]);
    } 
    a.swap(b);
    print(a);
    vector<int> dp{-inf};
    for (int i = 0; i < a.size(); ++i) {
        auto it = upper_bound(begin(dp), end(dp), a[i]);
        if (it == dp.end())
            dp.push_back(a[i]);
        else if (*it > a[i])
            *it = a[i];
    }
    cout << a.size() - (dp.size() - 1) + add;
    return 0;
}

• 서브태스크 1: 14 / 14
• 서브태스크 2: 21 / 21
• 서브태스크 3: 28 / 28
• 서브태스크 4: 37 / 37