제출 #1139634

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139634		mariemcharef	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	17 ms	6588 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll _Gcd(int a, int b) { return b == 0 ? a : _Gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a * b) / _Gcd(a, b); }

bool prime(int n)
{
    if (n < 2)
        return false;
    for (int x = 2; x * x <= n; x++)
        if (n % x == 0)
            return false;
    return true;
}

ll mod = 998244353;

ll power(ll a, ll b, ll mod = 1e9 + 7)
{
    ll result = 1;
    while (b > 0)
    {
        if (b & 1)
        {
            result = (result * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }
    return result;
}

int lowbit(int x)
{
    return x & (-x);
}

int xorFrom1To(int n)
{
    if (n % 4 == 0)
        return n;
    else if (n % 4 == 1)
        return 1;
    else if (n % 4 == 2)
        return n + 1;
    else
        return 0;
}

int factorial(int n)
{
    if (n <= 1)
        return 1;
    return n * factorial(n - 1);
}

/*const int MAX_N = 1e6;
// max_div[i] contains the largest prime that goes into i
int max_div[MAX_N + 1];

void seive() {
    for (int i = 2; i <= MAX_N; i++) {
        if (max_div[i] == 0) {
            for (int j = i; j <= MAX_N; j += i) { max_div[j] = i; }
        }
    }
}*/
vector<int> factor(int n)
{ // O (racine de n)
    vector<int> ret;
    for (int i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            ret.push_back(i);
            n /= i;
        }
    }
    if (n > 1)
    {
        ret.push_back(n);
    }
    return ret;
}
int phi(int n)
{ // counts the number of positive integers in the interval [1,n] which are coprime to n
    int ans = n;
    for (int p = 2; p * p <= n; p++)
    {
        if (n % p == 0)
        {
            while (n % p == 0)
            {
                n /= p;
            }
            ans -= ans / p;
        }
    }
    if (n > 1)
    {
        ans -= ans / n;
    }
    return ans;
}

void solve()
{
    ll n, t, s, m,d, q;
    cin >> n >> m;
    vector<ll> v(n),u, dp;
    for (int i = 0; i <n; i++){
        cin>>v[i];
    }
    for (int i = 1; i <=n; i++)
    {
        
        if(m*i>=v[i-1]) u.push_back(m*i-v[i-1]);
    }
    for (int i : u)
    {

        int pos = upper_bound(dp.begin(), dp.end(), i) - dp.begin();//upper instead of lower bc not strictly increesing
        if (pos == dp.size())
        {
            dp.push_back(i);
        }
        else 
        {
            dp[pos] = i;
        }
    }
    cout << n-dp.size() << endl;
}

int main()
{

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int q = 1;
    // cin >> q;
    while (q--)
    {
        solve();
    }
}

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