Submission #732249

#	Time	Username	Problem	Language	Result	Execution time	Memory
732249		amine_aroua	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	33 ms	8376 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vl vector<long long>
#define vs vector<string>
#define vii vector<pair<int,int>>
#define vll vector<pair<long long,long long>>
#define pb push_back
#define ll long long
#define ld long double
#define nl '\n'
#define boost ios::sync_with_stdio(false)
#define mp make_pair
#define se second
#define fi first
#define fore(i, y) for(ll i = 0; i < y; i++)
#define forr(i,x,y) for(int i = x;i<=y;i++)
#define forn(i,y,x) for(ll i = y; i >= x; i--)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define clr(v,k) memset(v,k,sizeof(v))
#define ub upper_bound
#define lb lower_bound

const ll MOD = 1e9 + 7;
const ll INF = 1e18 + 1;

ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)

// HERE IS THE SOLUTION

int main()
{
    cin.tie(0);
    cout.tie(0);
    boost;
    int n ,m;
    cin>>n>>m;
    vl a(n);
    fore(i , n)
    {
        cin>>a[i];
    }
    vl sq;
    vl dp;
    forr(i , 1 , n)
    {
        ll b = i * m - a[i-1];
        if(b >= 0)
        {
            sq.pb(b);
        }
    }
    for(ll x : sq)
    {
        int pos = upper_bound(all(dp) , x) - dp.begin();
        if(pos == sz(dp))
        {
            dp.pb(x);
        }
        else
        {
            dp[pos] = x;
        }
    }
    cout<<n-sz(dp)<<nl;
}

Compilation message (stderr)

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

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