Submission #1260322

#TimeUsernameProblemLanguageResultExecution timeMemory
1260322minhphanRabbit Carrot (LMIO19_triusis)C++17
0 / 100
1 ms328 KiB
#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üssel größer als b_i sein * => Longest non-increasing Subsequence für b * */ 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> dp; dp.push_back(0); //Hase startet bei Höhe 0 for(int k = 0; k<N; k++) { int value = a[k] - M*(k+1); 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); //1 wird addiert, da 0 der Startpunkt war return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...