Submission #680573

#	Time	Username	Problem	Language	Result	Execution time	Memory
680573		ethening	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	97 ms	10844 KiB

ho_t1

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	vector<pii> a(n + 1);
	vector<int> b(n);
	for (int i = 0; i < n + 1; i++) {
		int tmp;
		cin >> tmp;
		a[i] = make_pair(tmp, i);
	}
	for (auto &o: b) {
		cin >> o;
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	vector<int> pl(n + 1), pr(n + 1);
	for (int i = 0; i < n; i++) {
		if (i > 0) pl[i] = pl[i - 1];
		pl[i] = max(pl[i], max(a[i].first - b[i], 0));
		// cout << i << " " << pl[i] << endl;
	}
	for (int i = n - 1; i >= 0; i--) {
		if (i < n - 1) pr[i] = pr[i + 1];
		pr[i] = max(pr[i], max(a[i + 1].first - b[i], 0));
		// cout << i << ": " << pr[i] << endl;
	}
	vector<int> ans(n + 1);
	for (int i = 0; i <= n; i++) {
		if (i == 0) {
			ans[a[i].second] = pr[0];
		}
		else if (i == n) {
			ans[a[i].second] = pl[n - 1];
		}
		else {
			ans[a[i].second] = max(pl[i - 1], pr[i]);
		}
	}
	for (int i = 0; i <= n; i++) {
		cout << ans[i] << " \n"[i == n];
	}
}

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