Submission #1253486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253486		LucaLucaM	Constellation 3 (JOI20_constellation3)	C++17	35 / 100	1591 ms	38736 KiB

constellation3

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <map>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
 
  int n;
  std::cin >> n;

  std::vector<int> a(n);
  for (int i = 0; i < n; i++) {
    std::cin >> a[i];
  }

  int m;
  std::cin >> m;

  std::vector<std::vector<std::pair<int, int>>> stars(n);
  
  auto getLeq = [](int x, const std::map<int, ll> &mp) {
    ll ret = 0;
    for (const auto &[a, b] : mp) {
      if (a <= x) {
        ret = b;
      }
    }
    return ret;
    auto it = std::prev(mp.upper_bound(x));
    return (*it).second;
  };

  for (int i = 0; i < m; i++) {
    int x, y, c;
    std::cin >> x >> y >> c;
    x--;
    stars[x].push_back({y, c});
  }

  for (int i = 0; i < n; i++) {
    std::sort(stars[i].begin(), stars[i].end());
  }

  auto solve = [&](auto &&self, int l, int r) -> std::vector<ll> {
    if (l > r) {
      return std::vector<ll>(n + 1, 0);
    }
    if (l == r) {
      int m = l;
      std::vector<int> value(n + 1, 0);
      ll total = 0;
      for (const auto &[y, c] : stars[m]) {
        total += c;
        value[y] = c;
      }
      std::vector<ll> ret(n + 1, total);
      int maxi = 0;
      for (int i = 0; i <= n; i++)  {
        maxi = std::max(maxi, value[i]);
        ret[i] -= maxi;
      }
      return ret;
    }

    int m = l;
    for (int i = l + 1; i <= r; i++) {
      if (a[i] > a[m]) {
        m = i;
      }
    }

    auto st = self(self, l, m - 1);
    auto dr = self(self, m + 1, r);

    ll total = 0;
    std::vector<int> value(n + 1, 0);
    for (const auto &[y, c] : stars[m]) {
      total += c;
      value[y] = c;
    }
    
    std::vector<ll> here(n + 1, total);
    int maxi = 0;
    for (int i = 1; i <= n; i++) {
      maxi = std::max(maxi, value[i]);
      here[i] -= maxi;
    }
    std::vector<ll> ret(n + 1, 0);

    for (int x = 0; x <= a[m]; x++) {
      ret[x] = st[x] + dr[x] + here[x];
    } 
    for (int x = a[m] + 1; x <= n; x++) {
      ret[x] = st[a[m]] + dr[a[m]] + here[a[m]] + std::min({st[x] - st[a[m]], dr[x] - dr[a[m]], here[x] - here[a[m]]});
    }
    return ret;
  };

  auto root = solve(solve, 0, n - 1);
  ll answer = *std::min_element(root.begin(), root.end());
  std::cout << answer;
  
  return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 0 / 65