Submission #367096

#	Time	Username	Problem	Language	Result	Execution time	Memory
367096		buyolitsez	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	242 ms	15596 KiB

ho_t1

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define int ll

signed main() {
    int n;
    cin >> n;
    vector<int> b(n);
    vector <pair <int, int>> a(n + 1);
    for (int i = 0; i <= n; ++i) {
        int x;
        cin >> x;
        a[i] = {x, i};
    }
    for (auto &u : b) {
        cin >> u;
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    vector <int> preff(n + 1, 0), suff(n + 1, 0);
    vector <int> ans(n + 1);
    for (int i = 0; i < n; ++i) {
        int now = max(a[i].first - b[i], 0ll);
        preff[i] = now;
        if (i != 0) {
            preff[i] = max(preff[i], preff[i - 1]);
        }
    }
    preff[n] = preff[n - 1];
    for (int i = n - 1; i >= 0; --i) {
        int now = max(a[i + 1].first - b[i], 0ll);
        suff[i + 1] = now;
        if (i != n - 1) {
            suff[i + 1] = max(suff[i + 1], suff[i + 2]);
        }
    }
    suff[0] = suff[1];
    for (int i = 0; i <= n; ++i) {
        int pos = a[i].second;
        int now = 0;
        if (i != 0) {
            now += preff[i - 1];
        }
        if (i != n) {
            now = max(now, suff[i + 1]);
        }
        ans[pos] = now;
    }
    for (auto u : ans) {
        cout << u << ' ';
    }
}

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