Submission #876058

#	Time	Username	Problem	Language	Result	Execution time	Memory
876058		tinnhiemnn	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	63 ms	5380 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
#define file "file"
const long long N=2e5+5;
long long n,M,i,j,res,f[N];
vector<long long> v;

int main()
{
    //freopen(file".inp", "r", stdin);
    //freopen(file".out", "w", stdout);
    ios_base::sync_with_stdio(); cin.tie();

    cin>>n>>M;
    for (i=1;i<=n;i++)
    {
        cin>>j;
        if (M*i >= j) v.push_back(M*i-j);
    }

    if (v.size()==0) {cout<<n; return 0;}

    f[1]=v[0]; res=1;
    for (i=1;i<v.size();i++)
    {
        if (v[i]>=f[res]) {res++; f[res]=v[i]; continue;}

        j=upper_bound(f+1, f+res+1, v[i]) - f;
        f[j]=v[i];
    }

    cout<<n-res;
}

Compilation message (stderr)

triusis.cpp: In function 'int main()':
triusis.cpp:24:15: 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]
   24 |     for (i=1;i<v.size();i++)
      |              ~^~~~~~~~~

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