oj.uz

Submission #201608

# Submission time Handle Problem Language Result Execution time Memory
201608 2020-02-11T12:09:50 Z waynetuinfor Just Long Neckties (JOI20_ho_t1) C++17
0 / 100
 5 ms 376 KB 
#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
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Incorrect 5 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Incorrect 5 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 91.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Incorrect 5 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -