Submission #1214772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214772		dosts	Radio Towers (IOI22_towers)	C++20	0 / 100	14 ms	9260 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, inf = 2e9,LIM = 2010;

int sel = 0;
vi edges[LIM];
int dp[LIM][LIM];
int n;
vi h;
vi vals;
void init(int N, std::vector<int> H) {
  n = N;
  h = H;
  for (auto it : h) vals.push_back(it);
  sort(all(vals));
}

int idx(int x) {
  return upper_bound(all(vals),x)-vals.begin();
}

int cartesian(int L,int R) {
  int mx = -1,pick = -1;
  for (int i=L;i<=R;i++) {
    if (h[i] > mx) {
      pick = i;
      mx = h[i];
    }
  }
  if (L < pick) edges[pick].push_back(cartesian(L,pick-1));
  if (pick < R) edges[pick].push_back(cartesian(pick+1,R));
  return pick;
}

void dfs(int node,int p,int D) {
  for (int i=1;i<=n;i++) dp[node][i] = 0;
  vi opt1(n+1,0),opt2(n+1,0);
  for (auto it : edges[node]) {
    if (it == p) continue;
    dfs(it,node,D);
    for (int j = 1;j<=n;j++) {
      if (h[node] >= vals[j-1]+D) {
        opt1[j] += dp[it][j];
      }
    }
  }
  dp[node][idx(h[node])] = 1;
  for (int i=2;i<=n;i++) dp[node][i]=max(dp[node][i],max(opt1[i],dp[node][i-1]));
}

int dnq(int L,int R,int D) {
  for (int i=0;i<=n;i++) edges[i].clear();
  int root = cartesian(L,R);
  dfs(root,root,D);
  return dp[root][n];
} 

int max_towers(int L, int R, int D) {
  return dnq(L,R,D);
}

• 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