Submission #629576

#	Time	Username	Problem	Language	Result	Execution time	Memory
629576		somethingnew	Radio Towers (IOI22_towers)	C++17	0 / 100	4098 ms	3216 KiB

towers

#include "towers.h"

#include <cassert>
#include <cstdio>

#include <vector>
using namespace std;
vector<int> h;
struct segtree{
    int sz;
    vector<int> tree;
    void init(int n, vector<int> a) {
        sz = 1;
        while (sz < n)
            sz *= 2;
        tree.assign(sz * 2, 0);
        for (int i = 0; i < n; ++i) {
            tree[i + sz] = a[i];
        }
        for (int i = sz - 1; i > 0; --i) {
            tree[i] = tree[i * 2] + tree[i * 2 + 1];
        }
    }
    int get(int l, int r) {
        int res = 0;
        while (l <= r) {
            if (l & 1) {
                res += tree[l];
                l++;
            }
            if ((r & 1) == 0) {
                res += tree[r];
                r--;
            }
            l /= 2;r /= 2;
        }
        return res;
    }
};
segtree sg;

void init(int n, vector<int> hh) {
    h = hh;
    vector<int> bebra(n);
    for (int i = 1; i + 1 < n; ++i) {
        if (hh[i-1] > hh[i] and hh[i] < hh[i + 1])
            bebra[i] = 1;
    }
    sg.init(n, bebra);
}
int max_towers(int L, int R, int D) {
    if (D == 1) {
        int val = sg.get(L + 1, R - 1);
        if (L + 1 <= R and h[L] < h[L + 1])
            val++;
        if (L + 1 <= R and h[R-1] > h[R])
            val++;
        return max(val, 1);
    }
    vector<int> dp(h.size(), 1);
    int res = 0;
    for (int i = L; i < R; ++i) {
        int mx = h[i];
        res = max(res, dp[i]);
        for (int j = i + 1; j <= R; ++j) {
            mx = max(mx, h[j]);
            if (mx - D >= max(h[i], h[j]) and h[j - 1] > h[j] and (j == R or h[j + 1] > h[j])) {
                dp[j] = max(dp[j], dp[i] + 1);
            }
        }
    }
    res = max(res, dp[R]);
    return res;
}

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