Submission #784776

#	Time	Username	Problem	Language	Result	Execution time	Memory
784776		thimote75	Radio Towers (IOI22_towers)	C++17	11 / 100	4046 ms	1560 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>
using namespace std;

using idata = vector<int>;

idata heights;
int nbTowers;

void init(int N, idata H) {
  nbTowers = N;
  heights = H;
}

int max_towers(int L, int R, int D) {
  idata dp(nbTowers, 0);

  int res = 0;
  for (int i = R; i >= L; i --) {
    int mx = 0;

    int opt = heights[i];
    for (int j = i + 1; j <= R; j ++) {
      if (max(heights[i], heights[j]) + D <= opt)
        mx = max(mx, dp[j]);

      opt = max(opt, heights[j]);
    }

    dp[i] = mx + 1;
    res = max(res, dp[i]);
  }

  return res;
}

• 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