Submission #532528

#	Time	Username	Problem	Language	Result	Execution time	Memory
532528		amunduzbaev	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	98 ms	10836 KiB

ho_t1

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

#define ar array

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	vector<int> a(n + 1), b(n), p(n + 1);
	for(int i=0;i<=n;i++) cin>>a[i], p[i] = i;
	for(int i=0;i<n;i++) cin>>b[i];
	sort(b.begin(), b.end());
	sort(p.begin(), p.end(), [&](int i, int j){
		return (a[i] < a[j]);
	});
	
	vector<int> pref(n + 1), suff(n + 1);
	for(int i=0;i<n;i++){
		pref[i + 1] = max(pref[i + 1], a[p[i]] - b[i]);
		suff[i] = max(suff[i], a[p[i+1]] - b[i]);
	}
	
	for(int i=1;i<=n;i++) pref[i] = max(pref[i-1], pref[i]);
	for(int i=n-1;~i;i--) suff[i] = max(suff[i], suff[i+1]);
	vector<int> res(n + 1);
	for(int i=0;i<=n;i++){
		res[p[i]] = max(pref[i], suff[i]);
	}
	
	for(int i=0;i<=n;i++) cout<<res[i]<<" ";
	cout<<"\n";
}

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