Submission #448505

#	Time	Username	Problem	Language	Result	Execution time	Memory
448505		kakayoshi	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	36 ms	7440 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> data;
#define forw(i,a,b) for (ll i=a;i<=b;i++)
#define forb(i,a,b) for (ll i=a;i>=b;i--)
#define fast {ios::sync_with_stdio(false); cin.tie(0); }
#define fi first
#define se second
#define pu push
#define puf push_front
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fr front
#define all(a) a.begin(),a.end()
const ll oo=1e18;
const ll mod=1e9+7;
const ll maxN=2e5+5;
const int tx[4]={0,0,1,-1};
const int ty[4]={1,-1,0,1};
const ll base=31;
ll n,m,a[maxN];
vector <ll> save;
ll tinh()
{
    vector <ll> dp;
    for(auto i:save)
    {
        int pos=upper_bound(all(dp),i)-dp.begin();
        if (pos==dp.size()) dp.pb(i);
        else dp[pos]=i;
    }
    return dp.size();
}
void solve()
{
    cin>>n>>m;
    forw(i,1,n)
    {
        cin>>a[i];
        ll x=i*m-a[i];
        if (x>=0) save.pb(x);
    }
    cout<<n-tinh()<<endl;
}
int main()
{
    fast;
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
    int t=1; //cin>>t;
    while (t--)
        solve();
    return 0;
}

Compilation message (stderr)

triusis.cpp: In function 'll tinh()':
triusis.cpp:31:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         if (pos==dp.size()) dp.pb(i);
      |             ~~~^~~~~~~~~~~

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