Submission #241600

#	Time	Username	Problem	Language	Result	Execution time	Memory
241600		verngutz	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	127 ms	10888 KiB

ho_t1

#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
template <typename X, typename Y> istream& operator>>(istream& is, pair<X, Y>& p) { return is >> p.first >> p.second; }
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n), I(n + 1), ans(n + 1), dL(n), dR(n);
    cin >> a >> b;
    iota(I.begin(), I.end(), 0);
    sort(I.begin(), I.end(), [&](int i, int j) {
        return a[i] < a[j];
    });
    sort(b.begin(), b.end());
    for(int k = 0; k < n; k++) {
        dL[k] = max(a[I[k]] - b[k], 0);
        dR[k] = max(a[I[k + 1]] - b[k], 0);
    }
    partial_sum(dL.begin(), dL.end(), dL.begin(), [](int x, int y) { return max(x, y); });
    partial_sum(dR.rbegin(), dR.rend(), dR.rbegin(), [](int x, int y) { return max(x, y); });
    for(int k = 0; k <= n; k++) {
        ans[I[k]] = max(k ? dL[k - 1] : 0, k < n ? dR[k] : 0);
    }
    for(int i = 0; i <= n; i++) {
        cout << ans[i] << " ";
    }
    cout << endl;
    return 0;
}

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