Submission #1159025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159025		crispxx	Just Long Neckties (JOI20_ho_t1)	C++20	100 / 100	63 ms	13384 KiB

ho_t1

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define eb emplace_back
#define pb push_back
#define nl '\n'

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n; cin >> n;
	
	vector<int> a(n + 1), b(n);
	
	for(auto &x : a) cin >> x;
	
	for(auto &x : b) cin >> x;
	
	vector<pair<int, int>> v(n + 1);
	
	for(int i = 0; i <= n; i++) {
		v[i] = {a[i], i};
	}
	
	sort(all(v)), sort(all(b));
	
	vector<int> pref(n + 1), suf(n + 2);
	
	for(int i = 0; i < n; i++) {
		pref[i + 1] = max(pref[i], max(0LL, v[i].first - b[i]));
	}
	
	for(int i = n - 1; i >= 0; i--) {
		suf[i] = max(suf[i + 1], max(0LL, v[i + 1].first - b[i]));
	}
	
	// for(int i = 0; i <= n; i++) {
		// cout << v[i].first << ' ';
	// }
	
	// cout << nl;
	
	// for(int i = 0; i <= n; i++) {
		// cout << v[i].second << ' ';
	// }
	
	// cout << nl;
	
	// for(int i = 1; i <= n; i++) {
		// cout << pref[i] << ' ';
	// }
	
	// cout << nl;
	
	vector<int> ans(n + 1);
	
	for(int i = 0; i <= n; i++) {
		ans[v[i].second] = max(pref[i], suf[i]);
	}
	
	for(auto i : ans) cout << i << ' ';
	cout << nl;
}

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