Submission #1178267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178267		PagodePaiva	Radio Towers (IOI22_towers)	C++20	11 / 100	176 ms	14296 KiB

towers

#include<bits/stdc++.h>
#include "towers.h"
#include <vector>
#define fr first
#define sc second

using namespace std;

const int N = 2010;
int v[N];

struct Segtree{
    pair <int, int> tree[4*N];
    pair <int, int> join(pair <int, int> a, pair <int, int> b){
        if(a.fr > b.fr) return a;
        if(a.fr < b.fr) return b;
        if(a.sc > b.sc) return a;
        return b;
    }
    void build(int node, int l, int r){
        if(l == r){
            tree[node] = {v[l], l};
            return;
        }
        int mid = (l+r)/2;
        build(2*node, l, mid);
        build(2*node+1, mid+1, r);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
    }
    pair <int, int> query(int node, int l, int r, int tl, int tr){
        if(l > tr or tl > r) return {-1, 0};
        if(l <= tl and tr <= r) return tree[node];
        int mid = (tl+tr)/2;
        return join(query(2*node, l, r, tl, mid), query(2*node+1, l,r, mid+1, tr));
    }
} seg;
int n;

void init(int mm, std::vector<int> h) {
    n = mm;
    for(int i = 1;i <= n;i++)
        v[i] = h[i-1];
    seg.build(1, 1, n);
}

int dp[N][N];

int max_towers(int L, int R, int D) {
    L++;
    R++;
    for(int i = L-1;i <= R;i++){
        dp[L-1][i] = 0;
    }
    for(int i = L;i <= R;i++){
        for(int j = i+1;j <= R+1;j++){
            if(j == R+1){
                dp[i][j] = max(dp[i-1][j], dp[i-1][i]+1);
                continue;
            }
            dp[i][j] = max(dp[i-1][j], (seg.query(1, i+1, j-1, 1, n).first-D >= max(v[i], v[j]) ? dp[i-1][i]+1 : 0));
        }
    }
    return dp[R][R+1];
}

• 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