Submission #955405

#	Time	Username	Problem	Language	Result	Execution time	Memory
955405		debargha	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	63 ms	8388 KiB

triusis

//longest non-decreasing subsequence.....................
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int find(vector<int>&work)
{
    vector<int>lis;
    for(int i=0;i<work.size();i++)
    {
        auto it=upper_bound(lis.begin(),lis.end(),work[i]);
        if(it==lis.end())
        {
            lis.push_back(work[i]);
        }
        else
        {
            *it = work[i];
        }
    }
    return lis.size();
}
int32_t main()
{
    int n,M;
    cin>>n>>M;
    vector<int>v(n);
    for(int i=0;i<n;i++)
    {
        cin>>v[i];
    }
    vector<int>work;
    for(int i=1;i<=n;i++)
    {
        if(i*M>=v[i-1])
        {
            work.push_back(i*M - v[i-1]);
        }
    }
    cout<<n-find(work)<<endl;
}

Compilation message (stderr)

triusis.cpp: In function 'long long int find(std::vector<long long int>&)':
triusis.cpp:8:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     for(int i=0;i<work.size();i++)
      |                 ~^~~~~~~~~~~~

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