Submission #1226320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226320		piedav	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	18 ms	1988 KiB

triusis

//naive solution
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//alg written with help from chatGPT
int longestNonIncreasingSubseqFromZero(const std::vector<int>& v) {
    int n = v.size();
    // tails[L] = max possible last element of a nonincreasing subseq
    // of length L starting at v[0].
    // We'll use 1-based indexing on tails.
    std::vector<int> tails(n+1);
    
    int len = 1;
    tails[1] = v[0];  // subsequence of length 1 is just {v[0]}

    for (int i = 1; i < n; ++i) {
        int x = v[i];
        // find the largest L in [1..len] with tails[L] >= x
        int lo = 1, hi = len, pos = 0;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (tails[mid] >= x) {
                pos = mid;       // candidate
                lo = mid + 1;    // try to go further right
            } else {
                hi = mid - 1;
            }
        }
        // if pos==0, x > tails[1]=v[0], so it can't follow the 0
        if (pos == 0) continue;
        
        if (pos == len) {
            // we can extend the longest one
            tails[++len] = x;
        } else {
            // update the best tail for subseqs of length pos+1
            tails[pos + 1] = std::max(tails[pos + 1], x);
        }
    }

    return len;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<int> a (n+1, 0);
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i] -= m*i;
    }

    //find the longest nonincreasing subsequence starting with 0
    cout << n+1-(longestNonIncreasingSubseqFromZero(a));
    //cout << endl << ans;
}

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