Submission #1073481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073481		fv3	Radio Towers (IOI22_towers)	C++17	11 / 100	4070 ms	2012 KiB

towers

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

using namespace std;
const int INF = 1 << 30;

int N;
vector<int> H;

void init(int N_, vector<int> H_)
{
  N = N_;
  H = H_;
}

int max_towers(int L, int R, int D) 
{
  // You should always lease the smallest tower
  // No two adjacent towers can be leased

  int res = 0;
  vector<int> leased(N);
  vector<int> taken(N);
  while (true)
  {
    int mn = INF;
    int mn_index = -1;

    for (int i = L; i <= R; i++)
    {
      if (!leased[i] && !taken[i] && H[i] < mn)
      {
        mn = H[i];
        mn_index = i;
      }
    }
    if (mn == INF) break;

    bool ok = true;
    int mx = mn;
    for (int i = mn_index + 1; i <= R; i++)
    {
      if (leased[i])
      {
        if (mx - mn < D) 
        {
          taken[mn_index] = 1;
          ok = false;
          break;
        }
      }
      else
      {
        mx = max(mx, H[i]);
      }
    }
    if (!ok)
      continue;

    mx = mn;
    for (int i = mn_index - 1; i >= L; i--)
    {
      if (leased[i])
      {
        if (mx - mn < D)
        {
          taken[mn_index] = 1;
          ok = false;
          break;
        }
      }
      else
      {
        mx = max(mx, H[i]);
      }
    }
    if (!ok) continue;

    res++;
    leased[mn_index] = 1;
    if (mn_index > L) taken[mn_index-1] = 1;
    if (mn_index < R) taken[mn_index+1] = 1;
  }

  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