Submission #850938

#	Time	Username	Problem	Language	Result	Execution time	Memory
850938		olnyfcxwps	Radio Towers (IOI22_towers)	C++17	11 / 100	4089 ms	2632 KiB

towers

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Tower {
    int pos;
    int h;
}towers[100000];

int height[100000];
int tower_cnt;
bool picked[100000];

void init(int N, vector<int> H) {
    tower_cnt = N;
    for (int i = 0; i < N; i++) {
        height[i] = H[i];
        towers[i].h = H[i];
        towers[i].pos = i;
    }
}

bool cmp(struct Tower t1, struct Tower t2) {
    return t1.h < t2.h;
}

int max_towers(int L, int R, int D) {
    int ans = 0;
    sort(towers, towers + tower_cnt, cmp);
    /*for (int i = 0; i < tower_cnt; i++) {
        cout << towers[i].pos << "\n";
    }*/
    for (int i = 0; i < tower_cnt; i++) {
        int pos = towers[i].pos;
        if (pos < L || pos > R) {
            continue;
        }
        int h = towers[i].h;
        bool valid = true;

        int max_left = h;
        for (int j = pos - 1; j >= L; j--) {
            if (picked[j]) {
                if (max_left - D < height[j] || max_left - D < h) {
                    valid = false;
                    break;
                }
            }
            if (height[j] > max_left) {
                max_left = height[j];
            }
        }

        int max_right = h;
        for (int j = pos + 1; j <= R; j++) {
            if (picked[j]) {
                if (max_right - D < height[j] || max_right - D < h) {
                    valid = false;
                    break;
                }
            }
            if (height[j] > max_right) {
                max_right = height[j];
            }
        }

        if (valid) {
            picked[pos] = true;
            // cout << pos << "\n";
            ans += 1;
        }
    }
    return ans;
}

• 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