Submission #768904

#	Time	Username	Problem	Language	Result	Execution time	Memory
768904		1ne	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	76 ms	10836 KiB

ho_t1

/*
*  author : Apiram                  
*  created: 29.06.2023 02:12:41
*/

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;cin>>n;
	vector<pair<int,int>>arr(n + 1);
	for (int i = 0;i<=n;++i){
		cin>>arr[i].first;
		arr[i].second = i;
	}
	sort(arr.begin(),arr.end());
	vector<int>brr(n);
	for (int i = 0;i<n;++i){
		cin>>brr[i];
	}
	sort(brr.begin(),brr.end());
	vector<int>pref(n,0),suff(n + 1,0);
	for (int i = 0;i<n;++i){
		pref[i] = max(0,arr[i].first - brr[i]);
		if (i){
			pref[i]=max(pref[i - 1],pref[i]);
		}
	//	cout<<pref[i]<<" ";
	}
	//cout<<'\n';
	for (int i  = n;i > 0;--i){
		suff[i] = max(0,arr[i].first - brr[i - 1]);
		if (i != n){
			suff[i] = max(suff[i],suff[i + 1]);
		}
		//cout<<suff[i]<<" ";
	} 
	vector<int>ans(n + 1);
	for (int i = 0;i<=n;++i){
		ans[arr[i].second] = 0;
		if (i - 1>=0){
			ans[arr[i].second]=max(ans[arr[i].second],pref[i - 1]);
		}
		if (i + 1 <= n){
			ans[arr[i].second]=max(ans[arr[i].second],suff[i + 1]);
		}
	}
	for (auto x:ans){
		cout<<x<<" ";
	}
	cout<<'\n';
	return 0;
}

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