Submission #898483

#	Time	Username	Problem	Language	Result	Execution time	Memory
898483		Blagoj	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	83 ms	10952 KiB

ho_t1

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    pair<int, int> a[n + 1];
    for (int i = 0; i <= n; i++) cin >> a[i].first, a[i].second = i;
    sort(a, a + n + 1);
    int b[n];
    for (int i = 0; i < n; i++) cin >> b[i];
    sort(b, b + n);
    int leftAns[n + 1], rightAns[n + 1];
    leftAns[0] = max(a[0].first - b[0], 0);
    for (int i = 1; i < n; i++) leftAns[i] = max(leftAns[i - 1], max(a[i].first - b[i], 0));
    rightAns[n] = max(a[n].first - b[n - 1], 0);
    for (int i = n - 1; i > 0; i--) rightAns[i] = max(rightAns[i + 1], max(a[i].first - b[i - 1], 0));
    int ans[n + 1];
    for (int i = 0; i <= n; i++) {
        ans[a[i].second] = 0;
        if (i) ans[a[i].second]= max(ans[a[i].second], leftAns[i - 1]);
        if (i < n) ans[a[i].second]= max(ans[a[i].second], rightAns[i + 1]);
    }
    for (int i = 0; i <= n; i++) cout << ans[i] << " ";
}

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