Submission #881562

#	Time	Username	Problem	Language	Result	Execution time	Memory
881562		youssefbahy2022	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	23 ms	8380 KiB

triusis

//Rabbit Carrot
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <utility>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <climits>
#pragma GCC optimize("-Ofast")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#define ll long long
#define ull unsigned long long
#define Youssef_Bahy ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define Num_of_Digits(n) ((int)log10(n) + 1)
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define read(type) readInt<type>()
#define popcount(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
#define popcountll(x) __builtin_popcountll(x)
#define clzll(x) __builtin_clzll(x)
#define ctzll(x) __builtin_ctzll(x)
#define lg(x) 31-clz(x)
#define lgll(x) 63-clzll(x)
#define all(v) v.begin(),v.end()
using namespace std;
const int N=5000+5,INF=1e9;
const ll OO=1e118;
ll t=1;
int dr[]={1, 0, -1, 0};
int dc[]={0, 1, 0, -1};
void solve()
{
    ll n, m;
    cin>>n>>m;
    vector<ll>a(n);
    for(auto&x: a) cin>>x;
    vector<ll>dp;
    vector<ll>b;
    for(ll i=0;i<n;i++) {
        if(m*(i+1)-a[i]>=0) b.push_back(m*(i+1)-a[i]);
    }
    
    for(ll i=0;i<b.size();i++) {
        ll j=(int)(upper_bound(dp.begin(), dp.end(), b[i])-dp.begin());
        if(j==dp.size()) dp.push_back(b[i]);
        else dp[j]=b[i];
    }
    cout<<n-dp.size()<<'\n';
}
int main()
{
    Youssef_Bahy
//    cin>>t;
    while(t--)
        solve();
}

Compilation message (stderr)

triusis.cpp:39:13: warning: overflow in conversion from 'double' to 'long long int' changes value from '9.9999999999999997e+117' to '9223372036854775807' [-Woverflow]
   39 | const ll OO=1e118;
      |             ^~~~~
triusis.cpp: In function 'void solve()':
triusis.cpp:55:17: 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]
   55 |     for(ll i=0;i<b.size();i++) {
      |                ~^~~~~~~~~
triusis.cpp:57:13: 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]
   57 |         if(j==dp.size()) dp.push_back(b[i]);
      |            ~^~~~~~~~~~~

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