Submission #628681

#	Time	Username	Problem	Language	Result	Execution time	Memory
628681		kingmoshe	Radio Towers (IOI22_towers)	C++17	11 / 100	4085 ms	7924 KiB

towers

#include "towers.h"

#include <vector>
#include <iostream>
std::vector<int> real_h(0);
int maxi = 0;

void init(int N, std::vector<int> H) {
    real_h.resize(N);
    for (int i = 0; i < N; i++) {
        real_h[i] = H[i];
        if (real_h[i] > maxi) {
            maxi = real_h[i];
        }
    }

}

int get_max_id(int l, int r) {
    int max_result = real_h[l];
    int max_id =l;
    for (int i = l + 1; i <= r; i++) {
        if (real_h[i] > max_result) {
            max_result = real_h[i];
            max_id = i;
        }
    }
    return max_id;
}

int get_min_id(int l, int r) {
    int min_result= real_h[l];
    int min_id =l;
    for (int i = l + 1; i <= r; i++) {
        if (real_h[i] < min_result) {
            min_result = real_h[i];
            min_id = i;
        }
    }
    return min_id;
}
int max_towers2(int l, int r, int d, int max_possible_value) {
    if (l > r) {
        return 0;
    }
    if (l == r) {
        if (real_h[l] <= max_possible_value) {
            return 1;
        }
        return 0;
    }
    if (l + 1 == r) {
        if (real_h[l] <= max_possible_value || real_h[l + 1] <= max_possible_value) {
            return 1;
        }
        return 0;
    }
    int max_id = get_max_id(l, r);
    int left_value = max_towers2(l, max_id - 1, d, real_h[max_id] - d);
    int right_value = max_towers2(max_id + 1, r, d, real_h[max_id] - d);
    if (left_value + right_value == 0) {
        int min_id = get_min_id(l, r);
        if (real_h[min_id] <= max_possible_value) {
            return 1;
        }
    }
    return left_value + right_value;
}
int max_towers(int L, int R, int D) {
    return max_towers2(L, R, D, maxi);
}

/*int main() {
    init(7, std::vector<int>{10, 20, 60, 40, 50, 30, 70});
    std::cout << max_towers(1, 5, 10) << std::endl;
    std::cout << max_towers(2, 2, 100) << std::endl;
    std::cout << max_towers(0, 6, 17) << std::endl;

}*/

• Subtask 1: 0 / 4
• Subtask 2: 11 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23