Estrategia O(N³)

Primero se filtran posiciones con valores no nulos que no pueden ser máximos locales. El cálculo utiliza programación dinámica:

const int MAX_N = 4e5 + 5;
int n_values, sequence[MAX_N], cost[MAX_N]; 
bool is_visible[MAX_N]; 
ll dp_table[2005][2005];

int main() {
  cin >> n_values;
  for (int pos = 1; pos <= n_values; pos++) {
    cin >> sequence[pos];
    if (sequence[pos] != -1) is_visible[sequence[pos]] = true;
  }
  for (int idx = 1; idx <= n_values; idx++) cin >> cost[idx];

  int ptr = 0;
  for (int idx = 1; idx <= n_values; idx++) {
    if (sequence[idx] != -1) {
      if (ptr > sequence[idx]) cost[sequence[idx]] = 0;
    } else {
      while (is_visible[++ptr]);
    }
  }

  memset(dp_table, -0x3f, sizeof(dp_table));
  dp_table[0][0] = 0;
  
  for (int idx = 1; idx <= n_values; idx++) {
    if (sequence[idx] != -1) {
      for (int w = 0; w < sequence[idx]; w++) {
        dp_table[idx][sequence[idx]] = max(dp_table[idx][sequence[idx]], dp_table[idx-1][w] + cost[sequence[idx]]);
      }
      for (int w_val = sequence[idx] + 1; w_val <= n_values; w_val++) {
        dp_table[idx][w_val] = dp_table[idx-1][w_val];
      }
    } else {
      for (int w_val = 1; w_val <= n_values; w_val++) {
        dp_table[idx][w_val] = dp_table[idx-1][w_val];
        if (!is_visible[w_val]) {
          for (int k_val = 0; k_val < w_val; k_val++) {
            dp_table[idx][w_val] = max(dp_table[idx][w_val], dp_table[idx-1][k_val] + cost[w_val]);
          }
        }
      }
    }
    cout << *max_element(dp_table[idx], dp_table[idx] + n_values + 1) << " ";
  }
  return 0;
}

Optimización O(N²)

Se mejora mediante reducción de dimensionalidad y reestrucutración:

const int MAX_SIZE = 4e5 + 5; 
const ll INF_VALUE = 0x3f3f3f3f3f3f3f3f;
int n_elements, input_seq[MAX_SIZE], cost_arr[MAX_SIZE];
bool visibility_flag[MAX_SIZE];
ll modified_cost[MAX_SIZE], dp_arr[MAX_SIZE], tmp_dp[MAX_SIZE];

int main() {
  cin >> n_elements;
  for (int i = 1; i <= n_elements; i++) {
    cin >> input_seq[i];
    if (input_seq[i] != -1) visibility_flag[input_seq[i]] = true;
  }
  for (int j = 1; j <= n_elements; j++) cin >> cost_arr[j];

  int counter = 0;
  for (int j = 1; j <= n_elements; j++) {
    if (input_seq[j] != -1) {
      if (counter > input_seq[j]) cost_arr[input_seq[j]] = 0;
    } else {
      while (visibility_flag[++counter]);
    }
  }
  for (int j = 1; j <= n_elements; j++) {
    modified_cost[j] = visibility_flag[j] ? -INF_VALUE : cost_arr[j];
  }

  memset(dp_arr, -0x3f, sizeof(dp_arr));
  dp_arr[0] = 0;
  int upper_bound = 0;

  for (int idx = 1; idx <= n_elements; idx++) {
    if (input_seq[idx] != -1) {
      dp_arr[input_seq[idx]] = max(dp_arr[input_seq[idx]], dp_arr[input_seq[idx] - 1] + cost_arr[input_seq[idx]]);
      for (int j = 0; j < input_seq[idx]; j++) dp_arr[j] = -INF_VALUE;
    } else {
      for (int j = n_elements; j > upper_bound; j--) {
        dp_arr[j] = dp_arr[j - 1] + modified_cost[j];
      }
      dp_arr[0] = -INF_VALUE;
    }
    
    for (int j_val = 1; j_val <= n_elements; j_val++) {
      dp_arr[j_val] = max(dp_arr[j_val - 1], dp_arr[j_val]);
    }
    
    for (int j_val = 1; j_val <= n_elements; j_val++) {
      if (dp_arr[j_val] >= 0) {
        upper_bound = j_val;
        break;
      }
    }
    cout << dp_arr[n_elements] << " ";
  }
  return 0;
}

Implementación con Estructuras de Datos

Optimización final mediante segmentación y árboles de segmentos:

const int MAX_LIMIT = 8e5 + 5, BASE_OFFSET = 4e5 + 100;
const ll MAX_INF = 0x3f3f3f3f3f3f3f3f, EMPTY_VAL = -MAX_INF - 114514;
int total_size, data_points, cur_bound, cur_segment, input_data[MAX_LIMIT];
int cost_values[MAX_LIMIT], link_id[MAX_LIMIT];
bool exists_flag[MAX_LIMIT];
ll adjusted_cost[MAX_LIMIT], prefix_sum[MAX_LIMIT];

struct SegmentTree {
  /* Implementación de árbol de segmentos */
};

ll compute_value(int idx);
int binary_search_segment(int low, int high, int node);

int main() {
  cin >> total_size;
  for (int j = 1; j <= total_size; j++) {
    cin >> input_data[j];
    if (input_data[j] != -1) exists_flag[input_data[j]] = true;
  }
  for (int j = 1; j <= total_size; j++) cin >> cost_values[j];

  int count = 0;
  for (int j = 1; j <= total_size; j++) {
    if (input_data[j] != -1) {
      if (count > input_data[j]) cost_values[input_data[j]] = 0;
    } else {
      while (exists_flag[++count]);
    }
  }
  
  data_points = 0;
  for (int j = 1; j <= total_size; j++) {
    if (!exists_flag[j]) {
      adjusted_cost[++data_points] = cost_values[j];
    }
    link_id[j] = data_points;
  }
  for (int j = 1; j <= data_points; j++) {
    prefix_sum[j] = prefix_sum[j - 1] + adjusted_cost[j];
  }

  /* Configuración de árboles de segmentos */
  
  int shift_value = 0;
  cur_bound = cur_segment = 0;
  for (int idx = 1; idx <= total_size; idx++) {
    if (input_data[idx] != -1) {
      if (cur_bound < input_data[idx]) {
        int seg_id = link_id[input_data[idx]];
        ll new_val = compute_value(seg_id + BASE_OFFSET - shift_value) + cost_values[input_data[idx]];

        /* Buscar punto de división y actualizar valores */
        int split_pos = binary_search_segment(seg_id + BASE_OFFSET - shift_value, data_points + BASE_OFFSET - shift_value, new_val);
        
        /* Aplicar actualización en segmento */
        update_segment(seg_id + BASE_OFFSET - shift_value, split_pos, new_val);
        cur_bound = input_data[idx];
        cur_segment = seg_id;
      }
    } else {
      /* Proceso para valores indeterminados */
      shift_value++;
      reset_segment(BASE_OFFSET - shift_value);
      if (!cur_segment) cur_segment = cur_bound = 1;
    }
    cout << compute_value(data_points + BASE_OFFSET - shift_value) << " ";
  }
  return 0;
}