Submission #202051

#	Time	Username	Problem	Language	Result	Execution time	Memory
202051		JustInCase	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	136 ms	7036 KiB

ho_t1

#include <bits/stdc++.h>

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int32_t n;
	std::cin >> n;

	std::vector< std::pair< int32_t, int32_t > > a(n + 1);
	for(int32_t i = 0; i < n + 1; i++) {
			std::cin >> a[i].first;
			a[i].second = i;
	}

	std::vector< int32_t > b(n);
	for(int32_t i = 0; i < n; i++) {
		std::cin >> b[i];
	}

	std::sort(a.begin(), a.end());
	std::sort(b.begin(), b.end());

	std::vector< int32_t > prefMax(n), suffMax(n);
	for(int32_t i = 0; i < n; i++) {
		if(i != 0) {
			prefMax[i] = prefMax[i - 1];
		}
		else {
			prefMax[i] = 0;
		}

		prefMax[i] = std::max(prefMax[i], a[i].first - b[i]);	
	}

	for(int32_t i = n - 1; i >= 0; i--) {
		if(i != n - 1) {
			suffMax[i] = suffMax[i + 1];
		}
		else {
			suffMax[i] = 0;
		}
		
		suffMax[i] = std::max(suffMax[i], a[i + 1].first - b[i]);
	}
	
	std::vector< int32_t > ans(n + 1);

	ans[a[0].second] = suffMax[0];
	for(int32_t i = 1; i <= n - 1; i++) {
		ans[a[i].second] = std::max(prefMax[i - 1], suffMax[i]);
	}
	ans[a[n].second] = prefMax[n - 1];
	
	for(auto &x : ans) {
		std::cout << x << " ";
	}
	std::cout << '\n';
}

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