Submission #762920

#	Time	Username	Problem	Language	Result	Execution time	Memory
762920		vjudge1	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	95 ms	10120 KiB

ho_t1

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

#define int long long

const int NM = 2e5;

struct necktie{
	int id, l;
};

int N, B[NM+5], pref[NM+5], cur = 0, ans[NM+5];
necktie A[NM+5];

bool cmp(necktie a, necktie b){
	return a.l < b.l;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N+1; i++){
		cin >> A[i].l;
		A[i].id = i;
	}
	for (int i = 1; i <= N; i++)
		cin >> B[i];
	sort(B+1, B+1+N);
	sort(A+1, A+1+N+1, cmp);
	
	for (int i = 1; i <= N; i++)
		pref[i] = max(pref[i-1], max(A[i].l-B[i], 0LL));
	cur = 0;
	ans[A[N+1].id] = pref[N];
	for (int i = N; i >= 1; i--){
		cur = max(cur, max(A[i+1].l-B[i], 0LL));
		ans[A[i].id] = max(pref[i-1], cur);
	}
	for (int i = 1; i <= N+1; i++) cout << ans[i] << ' ';
	return 0;
}

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