Submission #337275

#	Time	Username	Problem	Language	Result	Execution time	Memory
337275		ram	Just Long Neckties (JOI20_ho_t1)	C++14	0 / 100	1 ms	364 KiB

ho_t1

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

int main() {
  	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	
	pair<int, int> a[n+1];
	int b[n];
	
	for (int i = 0; i < n+1; i++) {
		cin >> a[i].first;
		a[i].second = i;
	}
	
	for (int i = 0; i < n; i++) {
		cin >> b[i];
	}
	
	sort(a, a+n+1);
	sort(b, b+n);
	
	int same[n]; // max( sorted a[i] - sorted b[i] , 0 ) (i goes from 0 to n-1 inclusive)
	int diff[n]; // max( sorted a[i+1] - sorted b[i], 0 ) (i goes from 0 to n-1 inclusive)
	
	for (int i = 0; i < n; i++) {
		same[i] = a[i].first - b[i];
		if (same[i] < 0) same[i] = 0;
		diff[i] = a[i+1].first - b[i];
		if (diff[i] < 0) diff[i] = 0;
	}
	
	int maxsame[n];
	int maxdiff[n];
	
	maxsame[0] = same[0];
	maxdiff[n-1] = diff[n-1];
	
	for (int i = 1; i < n; i++) {
		maxsame[i] = max(maxsame[i-1], same[i]);
	}
	
	for (int i = n-2; i >= 0; i--) {
		maxdiff[i] = max(maxdiff[i+1], diff[i]);
	}
	
	int ans[n+1];
	
	for (int i = 0; i < n+1; i++) {
		int index = a[i].second;
		if (index == 0) {
			ans[index] = maxdiff[index];
		} else if (index == n) {
			ans[index] = maxsame[index-1];
		} else {
			ans[index] = max(maxsame[index-1], maxdiff[index]);
		}
	}
	
	for (int i = 0; i < n; i++) {
		cout << ans[i] << " ";
	}
	cout << ans[n];
}

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