Submission #832482

#	Time	Username	Problem	Language	Result	Execution time	Memory
832482		fatemetmhr	Radio Towers (IOI22_towers)	C++17	11 / 100	4073 ms	5984 KiB

towers

// komak!

#include "towers.h"
#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define mp       make_pair
#define pb       push_back

typedef long long ll;

const ll mod   = 1e9 + 7;
const int maxn5 = 1e5 + 10;

int mxid, h[maxn5];
int n, dp[maxn5], dp2[maxn5];
pair <int, int> per[maxn5];

void solve(int l, int r, int d){
    if(r <= l)
        return;
    int mid = l;
    for(int i = l + 1; i < r; i++)
        if(h[i] > h[mid])
            mid = i;
    solve(l, mid, d);
    solve(mid + 1, r, d);
    for(int i = l; i < r; i++)
        per[i] = {h[i], i};
    sort(per + l, per + r);
    int mx1 = 0, mx2 = 0;
    for(int i = l; i < r; i++){
        if(per[i].se < mid)
            mx1 = max(mx1, dp[per[i].se]);
        if(per[i].se > mid)
            mx2 = max(mx2, dp[per[i].se]);
        dp2[i] = max(mx1, mx2);
        if(per[i].fi + d <= per[r - 1].fi)
            dp2[i] = mx1 + mx2;
    }
    dp2[r - 1] = max(dp2[r - 1], 1);
    for(int i = l; i < r; i++){
        h[i] = per[i].fi;
        dp[i] = dp2[i];
    }
}

void init(int N, std::vector<int> H) {

    mxid = 0;
    n = N;
    for(int i = 0; i < n; i++){
        h[i] = H[i];
        if(h[i] > h[mxid])
            mxid = i;
    }

}

int max_towers(int l, int r, int d) {

    solve(l, r + 1, d);
    return (*max_element(dp, dp + n));

}

• 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