Submission #713399

#	Time	Username	Problem	Language	Result	Execution time	Memory
713399		mtxas	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	84 ms	4788 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    const int inf = 0x3f3f3f3f;
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    /// solve it
    vector<int> b;
    for(int i = 1; i <= n; ++i)
    {
        if(a[i] <= i * m)
        {
            b.push_back(i * m - a[i]);
        }
    }
    auto lis = [&] (vector<int> &v) -> int
    {
        int maxlen = 0;
        vector<int> dp(v.size());
        for(int i = 0; i < v.size(); ++i)
        {
            int x = upper_bound(dp.begin(), dp.begin() + maxlen, v[i]) - dp.begin();
            if(x == maxlen)
            {
                maxlen++;
            }
            dp[x] = v[i];
        }
        return maxlen;
    };
    cout << n - lis(b) << '\n';
}
signed main()
{
    solve();
}

Compilation message (stderr)

triusis.cpp: In lambda function:
triusis.cpp:26:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int i = 0; i < v.size(); ++i)
      |                        ~~^~~~~~~~~~
triusis.cpp: In function 'void solve()':
triusis.cpp:5:15: warning: unused variable 'inf' [-Wunused-variable]
    5 |     const int inf = 0x3f3f3f3f;
      |               ^~~

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