Submission #833726

#	Time	Username	Problem	Language	Result	Execution time	Memory
833726		kevinsogo	Dancing Elephants (IOI11_elephants)	C++17	0 / 100	0 ms	212 KiB

elephants

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

#ifdef LOCAL
bool debug = true;
#else
bool debug = false;
#endif

int n, L;
vector<int> x, best;

void init(int N, int L, int X[]) {
    n = N;
    ::L = L;
    x.resize(n);
    best.resize(n + 1);
    for (int i = 0; i < n; i++) {
        x[i] = X[i];
    }
}

int update(int i, int y) {
    if (debug) { cerr << "DOING UPDATE " << i << " " << y << endl; }
    if (debug) { cerr << "INITIALLY:    "; }
    if (debug) { for (int t = 0; t < n; t++) cerr << x[t] << " "; cerr << endl; }
    x[i] = y;
    while (i + 1 < n and x[i] > x[i + 1]) {
        swap(x[i], x[i + 1]);
        i++;
    }
    while (i - 1 >= 0 and x[i - 1] > x[i]) {
        swap(x[i - 1], x[i]);
        i--;
    }
    if (debug) { cerr << "AFTER UPDATE: "; }
    if (debug) { for (int t = 0; t < n; t++) cerr << x[t] << " "; cerr << endl; }

    int prev = -1;

    for (int i = 0; i < n; i++) {
        while (prev + 1 < i and x[prev + 1] <= x[i] - L - 1) {
            prev++;
        }
        best[i + 1] = best[prev + 1] + 1;
    }
    return best[n];
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3