Submission #866032

#	Time	Username	Problem	Language	Result	Execution time	Memory
866032		ThylOne	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	156 ms	15468 KiB

ho_t1

//####################
//Neckties
//####################
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define FLAG(x) cerr<<"FLAG("<<#x<<")";
typedef pair<int,int> pii;
const int INF = 1000*1000;
signed main(){
	int n;cin>>n;
	vector<int> bases(n);
	vector<pii> neckties(n+1);
	for(int i=0;i<=n;i++){
		int v;cin>>v;
		neckties[i] = make_pair(v,i);
	}
	for(int i=0;i<n;i++){cin>>bases[i];}
	sort(bases.begin(),bases.end());
	sort(neckties.begin(),neckties.end());
	int Suffix[n+1];
	int Prefix[n+1];
	Suffix[n]=-INF;
	Prefix[0]=-INF;

	for(int i=n-1;i>=0;i--){
		Suffix[i] = max(Suffix[i+1],max(neckties[i+1].first-bases[i],(long long)0));
	}
	for(int i=1;i<=n;i++){
		Prefix[i] = max(Prefix[i-1],max(neckties[i-1].first-bases[i-1],(long long)0));
	}
	int ans[n+1];
	for(int i=0;i<=n;i++){
		ans[neckties[i].second] = max(Prefix[i],Suffix[i]);
	}
	for(int i=0;i<=n;i++){
		cout<<ans[i]<<' ';
	}
	cout<<endl;
	return 0;
};

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