Submission #1313337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313337		nicolo_010	Just Long Neckties (JOI20_ho_t1)	C++20	100 / 100	66 ms	7108 KiB

ho_t1

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define f first
#define s second

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n; cin >> n;
	vector<pii> a(n+1);
	for (int i=0; i<=n; i++) {
		cin >> a[i].first;
		a[i] = {a[i].first, i};
	}
	vector<int> b(n);
	for (int i=0; i<n; i++) {
		cin >> b[i];
	}
	vector<int> ans(n+1);
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	vector<int> pref(n, 0);
	pref[0] = max(0, a[0].first-b[0]);
	for (int i=1; i<n; i++) {
		pref[i] = max(pref[i-1], max(0, a[i].first-b[i]));
	}
	vector<int> suf(n, 0);
	suf[n-1] = max(0, a[n].first-b[n-1]);
	for (int i=n-2; i>=0; i--) {
		suf[i] = max(suf[i+1], max(0, a[i+1].first-b[i]));
	}
	for (int i=0; i<=n; i++) {
		int left = (i==0 ? 0 : pref[i-1]);
		int right = (i==n ? 0 : suf[i]);
		ans[a[i].second] = max(left, right);
	}
	for (auto x : ans) {
		cout << x << " ";
	}
	cout << "\n";
}

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