Submission #932609

#	Time	Username	Problem	Language	Result	Execution time	Memory
932609		lssply	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	21 ms	4304 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
//#define cin fin
//#define cout fout
ifstream  fin("cowjog.in");
ofstream fout("cowjog.out");

const int maxNr=2e5, mod=1e9+7, inf=2e9;
int n, m, x, a[maxNr+1];
vector<int>dp;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        cin >> x;
        a[i]=m*i-x;
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]>=0)
        {
            int l=upper_bound(dp.begin(), dp.end(), a[i])-dp.begin();
            if(l==dp.size())
            {
                dp.push_back(a[i]);
            }
            else
            {
                dp[l]=a[i];
            }
        }
    }
    cout << n-dp.size();


    return 0;
}

Compilation message (stderr)

triusis.cpp: In function 'int main()':
triusis.cpp:28:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |             if(l==dp.size())
      |                ~^~~~~~~~~~~

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