Submission #1114633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114633		AdamGS	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	80 ms	15804 KiB

ho_t1

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAX=2*1e5+7;

vector<pair<ll, ll>> a;
vector<ll> b;
ll wyn[MAX];
ll pref[MAX];
ll suf[MAX];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n, c;
    cin >> n;

    for (int i=0; i<=n; i++){
        cin >> c;
        a.push_back({c, i});
    }

    for (int i=0; i<n; i++){
        cin >> c;
        b.push_back(c);
    }

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    pref[0] = 0;
    for (int i=1; i<=n; i++){
        pref[i] = max(pref[i-1], max((ll)0, a[i-1].first-b[i-1]));
    }

    suf[n+1] = 0;

    for (int i=n; i>=1; i--){
        suf[i] = max(suf[i+1], max((ll)0, a[i].first-b[i-1]));
    }

    for (int i=0; i<=n; i++){
        wyn[a[i].second] = max(pref[i], suf[i+1]);
    }

    for (int i=0; i<=n; i++) cout << wyn[i] << " ";

    return 0;
}

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