Submission #815760

#	Time	Username	Problem	Language	Result	Execution time	Memory
815760		AmrT	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	66 ms	5440 KiB

triusis

#include <bits/stdc++.h>
#define lop(i,a,b) for(ll i = a; i < b; i++)
#define alop(i,v) for(auto &i: v)
#define in(v) for(auto &i: v) cin >> i;
#define ll long long
#define endl '\n'
#define pb push_back
#define all(v) v.begin(),v.end()
#define mem(p, x) memset(p, x, sizeof(p))
using namespace std;
ll mod = 1e9 + 7;

ll cmp(pair<ll, ll> a, pair<ll, ll> b){
    if(a.first == b.second) return a.second < b.second;
    return a.first > b.first;
}


int main(){
    ll n, m, t; cin >> n >> m;
    vector<ll> arr;
    lop(i, 0, n){ 
        cin >> t; t = m * (i + 1) - t;
        if(t >= 0) arr.pb(t);
    }
    vector<ll> dp(arr.size() + 1, 1e18); dp[0] = -2e18;
    alop(i, arr) dp[upper_bound(all(dp), i) - dp.begin()] = i;

    ll ans = 1;
    while(ans <= arr.size()){
        if(dp[ans] == 1e18) break;
        ans++;
    }
    ans--;

    cout << n - ans;

// arr[j] + m * (i - j) >= arr[i]
// arr[j] + m*i - m*j >= arr[i]
// arr[j] - m*j >= arr[i] - m*i
    return 0;
}

Compilation message (stderr)

triusis.cpp: In function 'int main()':
triusis.cpp:30: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]
   30 |     while(ans <= arr.size()){
      |           ~~~~^~~~~~~~~~~~~

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