Submission #201609

#	Time	Username	Problem	Language	Result	Execution time	Memory
201609		waynetuinfor	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	128 ms	7032 KiB

ho_t1

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  int n;
  std::cin >> n;
  std::vector<int> a(n + 1), b(n), od(n + 1);
  for (int i = 0; i < n + 1; ++i) std::cin >> a[i];
  for (int i = 0; i < n; ++i) std::cin >> b[i];
  std::sort(b.begin(), b.end());
  std::iota(od.begin(), od.end(), 0);
  std::sort(od.begin(), od.end(), [&a](int i, int j) { return a[i] < a[j]; });
  std::vector<int> pref(n), suff(n + 1);
  for (int i = 0; i < n; ++i) {
    pref[i] = std::max(0, a[od[i]] - b[i]);
    if (i > 0) pref[i] = std::max(pref[i], pref[i - 1]);
  }
  for (int i = n; i > 0; --i) {
    suff[i] = std::max(0, a[od[i]] - b[i - 1]);
    if (i < n) suff[i] = std::max(suff[i], suff[i + 1]);
  }
  std::vector<int> ans(n + 1);
  for (int i = 0; i < n + 1; ++i) {
    int g = 0;
    if (i > 0) g = std::max(g, pref[i - 1]);
    if (i + 1 <= n) g = std::max(g, suff[i + 1]);
    ans[od[i]] = g;
  }
  for (int i = 0; i < n + 1; ++i) std::cout << ans[i] << " ";
  std::cout << "\n";
  return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 8 / 8
• Subtask 3: 91 / 91