제출 #1166621

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166621		khoile08	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	17 ms	6588 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define FOD(i,a,b) for(int i = a; i >= b; i--)
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define lcm(a,b) (a*b)/__gcd(a,b)
#define ii pair<int,int>
#define iii pair<int,pair<int,int>>
#define iv pair<pair<int,int>,pair<int,int>>
#define sq(a) (a) * (a)

const int inf = 1e9;
const ll INF = 1e18;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;

const int dx[] = {-1,0,1,0};
const int dy[] = {0,1,0,-1};
const int dxx[] = {-1,-1,0,1,1,1,0,-1};
const int dyy[] = {0,1,1,1,0,-1,-1,-1};

/*
Thay vì đếm số thay đổi ít nhất, tính số giữ lại nhiều nhất:
Khi giữ lại i, ta có thể giữ lại k nếu
 (a[i] - a[k]) / (i - k) <= m
⇔ ai <= ak +  m * (i - k)
⇔ ai <= ak + m * i - m * k
⇔ ai - m * i <= ak - m * k
⇔ ci <= ck (ci = ai - mi * i)
=> tìm dãy con ko tăng
*/

int n, m;
vector<ll> dp, c;
ll a[N];

void solve()
{
    FOR(i,1,n)
        if(i * m >= a[i])
            c.pb(a[i] - m * i);
    if(c.empty())
    {
        cout << n << '\n';
        return;
    }
    dp.pb(c[(int)c.size()-1]);
    FOD(i,(int)c.size()-2,0)
    {
        int pos = upper_bound(dp.begin(), dp.end(), c[i]) - dp.begin();
        if(pos == dp.size()) dp.pb(c[i]);
        else dp[pos] = c[i];
    }
    cout << n - dp.size() << '\n';
}

signed main()
{
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int test = 1;
//    cin >> test;
    while(test--)
    {
        cin >> n >> m;
        FOR(i,1,n) cin >> a[i];
        solve();
    }
}

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