Submission #1260339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260339		minhphan	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	11 ms	3516 KiB

triusis

#include <bits/stdc++.h>
#include <vector>

using namespace std;

constexpr int BUF_SZ = 1 << 15;

inline namespace Input {
    char buf[BUF_SZ];
    int pos;
    int len;

    char next_char() {
        if (pos == len) {
            pos = 0;
            len = static_cast<int>(fread(buf, 1, BUF_SZ, stdin));
            if (!len) { return EOF; }
        }
        return buf[pos++];
    }

    int read_int() {
        char ch;
        int sgn = 1;
        while (!isdigit(ch = next_char())) {
            if (ch == '-') { sgn *= -1; }
        }
        int x = ch - '0';
        while (isdigit(ch = next_char())) { x = x * 10 + (ch - '0'); }
        return x * sgn;
    }
}

inline namespace Output {
    char buf[BUF_SZ];
    int pos;

    void flush_out() {
        fwrite(buf, 1, pos, stdout);
        pos = 0;
    }

    void write_char(const char c) {
        if (pos == BUF_SZ) { flush_out(); }
        buf[pos++] = c;
    }

    void write_int(int x) {
        static char num_buf[100];
        if (x < 0) {
            write_char('-');
            x *= -1;
        }
        int len = 0;
        for (; x >= 10; x /= 10) { num_buf[len++] = static_cast<char>('0' + (x % 10)); }
        write_char(static_cast<char>('0' + x));
        while (len) { write_char(num_buf[--len]); }
        write_char('\n');
    }

    // auto-flush output when the program exits
    void init_output() { assert(atexit(flush_out) == 0); }
}

/*
 * Idee: Statt die Anzahl der zu verändernden Blöcke zu minimieren, soll die Anzahl der feststehenden Blöcke maximiert werden.
 * Für feststehende Blöcke gilt (i>j): a_i-a_j<=M*(i-j), da jeder Turm nur maximal an Höhe M gewinnen kann.
 * => a_i-M*k<=a_j-M*k => (mit b_k=a_k-M*k) b_i<=b_j, d.h. alle b-Werte vor i, müssen größer als b_i sein
 * => Longest non-increasing Subsequence für b
 *
 * Zudem ist a_i<=M*i => a_i-M_i<=0
 */

int solveLNDS(vector<int> &plnds) {
    vector<int> dp;
    for (int i : plnds) {
        int pos = upper_bound(dp.begin(), dp.end(), i) - dp.begin();
        if (pos == dp.size()) {
            dp.push_back(i);
        } else {
            dp[pos] = i;
        }
    }
    return dp.size();
}

int main() {
    init_output();

    int N = read_int();
    int M = read_int();

    vector<int> a(N);

    for (int i = 0; i<N; i++) {
        a[i] = read_int();
    }

    vector<int> lnds;

    for (int k = 1; k<=N; k++) {
        if (k*M>= a[k-1]) {
            lnds.push_back(k*M-a[k-1]);
        }
    }

    write_int(N - solveLNDS(lnds));

    /*vector<int> dp;

    for(int k = 0; k<N; k++) {
        int value = a[k] - M*k;
        //if (value > 0) continue;
        int low = 0;
        int high = dp.size();
        while (low < high) { //Absteigende Liste
            int m = (low + high)/2;
            if (dp[m] >= value) {
                low = m + 1; //rechte Seite
            } else {
                high = m; //linke Seite
            }
        }
        if (low == dp.size()) {
            dp.push_back(value);
        } else {
            dp[low] = value;
        }
    }

    write_int(N-dp.size()); //1 wird addiert, da 0 der Startpunkt war*/
    return 0;
}

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