Submission #1014662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014662		snpmrnhlol	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	155 ms	11616 KiB

ho_t1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5;
int v[N + 1];
int p[N + 1];
ll sf[N + 1];
int v2[N];
ll ans[N + 1];
int main(){
    int n;
    cin>>n;
    for(int i = 0;i < n + 1;i++){
        cin>>v[i];
        p[i] = i;
    }
    for(int i = 0;i < n;i++){
        cin>>v2[i];
    }
    sort(p, p + n + 1,[&](int a,int b){
         return v[a] < v[b];
    });
    sort(v2,v2 + n);
    for(int i = n;i >= 1;i--){
        sf[i] = max((i != n?sf[i + 1]:0ll),(ll)max(0,v[p[i]] - v2[i - 1]));
    }
    ll cur = 0;
    for(int i = 0;i <= n;i++){
        ans[p[i]] = max(cur,(i == n?0:sf[i + 1]));
        //cout<<cur<<' '<<(i == n?0:sf[i + 1])<<' '<<p[i]<<'\n';
        if(i != n)cur = max(cur,(ll)max(v[p[i]] - v2[i],0));
    }
    for(int i = 0;i <= n;i++){
        cout<<ans[i]<<' ';
    }
    return 0;
}

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