Submission #628479

#	Time	Username	Problem	Language	Result	Execution time	Memory
628479		600Mihnea	Radio Towers (IOI22_towers)	C++17	11 / 100	4074 ms	1856 KiB

towers

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

using namespace std;

int glob_n;
vector<int> glob_h;

void init(int nn, vector<int> hh) {
  glob_n = nn;
  glob_h = hh;
}

int max_towers(int l, int r, int d) {
  assert(0 <= l && l <= r && r < glob_n);
  vector<int> inds;
  for (int i = l; i <= r; i++) {
    inds.push_back(i);
  }
  sort(inds.begin(), inds.end(), [&] (int i, int j) {
       return glob_h[i] < glob_h[j];});
  vector<bool> used(r - l + 1, 0);
  int solution = 0;
  for (auto &i : inds) {
    bool ok = 1;
    int mx = 0;
    for (int j = i + 1; j <= r && ok; j++) {
      if (used[j - l] && mx < glob_h[i] + d) {
        ok = 0;
      }
      mx = max(mx, glob_h[j]);
    }
    mx = 0;
    for (int j = i - 1; j >= l && ok; j--) {
      if (used[j - l] && mx < glob_h[i] + d) {
        ok = 0;
      }
      mx = max(mx, glob_h[j]);
    }
    solution += ok;
    used[i - l] = ok;
  }
  return solution;
}

• 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