Submission #940887

#	Time	Username	Problem	Language	Result	Execution time	Memory
940887		LittleOrange	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	76 ms	13908 KiB

ho_t1

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n;
    cin >> n;
    vector<ll> a(n+1),b(n);
    for(ll &i : a) cin >> i;
    for(ll &i : b) cin >> i;
    sort(b.begin(),b.end());
    vector<pair<ll,ll>> c(n+1);
    for(ll i = 0;i<=n;i++) c[i] = {a[i],i};
    sort(c.begin(),c.end());
    ll cur = 0;
    vector<ll> ans(n+1);
    for(ll i = 0;i<n;i++) cur = max({cur,0ll,c[i].first-b[i]});
    for(ll i = n;i>=0;i--){
        ans[c[i].second] = cur;
        if(i){
            cur = max({cur,0ll,c[i].first-b[i-1]});
        }
    }
    for(ll i = 0;i<=n;i++) cout << ans[i] << " \n"[i==n];
}

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