Submission #740808

#	Time	Username	Problem	Language	Result	Execution time	Memory
740808		josanneo22	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	104 ms	10792 KiB

ho_t1

#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second

void solve(){
	int n; cin>>n;
	vector<int> a(n+1),b(n);
	for(auto&x:a) cin>>x;
	for(auto&x:b) cin>>x;
    vector<int> ord(n+1);
    iota(ord.begin(),ord.end(),0);
    sort(ord.begin(),ord.end(),[&](int i,int j){
        return a[i]<a[j];
    });
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
	vector<int> pre(n+2),suf(n+2);
	pre[0]=max(0,a[0]-b[0]);
	for(int i=1;i<n;i++){
		pre[i]=max(pre[i-1],max(0,a[i]-b[i]));
	}
	suf[n-1]=max(0,a[n]-b[n-1]);
	for(int i=n-2;i>=0;i--){
		suf[i]=max(suf[i+1],max(0,a[i+1]-b[i]));
	}
    vector<int> ans(n+1);
    for(int i=0;i<n;i++){
        ans[ord[i]]=max(pre[i-1],suf[i]);
    }
    ans[ord[n]]=pre[n-1];
    for(int i=0;i<=n;i++){
        cout<<ans[i]<<' ';
    }
    cout<<'\n';
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	solve();
}

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