Submission #1297515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297515		muhammad-ahmad	Just Long Neckties (JOI20_ho_t1)	C++20	100 / 100	75 ms	15008 KiB

ho_t1

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include <numeric>
#include <stack>
#include <chrono>
using namespace std;

void fast_io(){
	// freopen("", "r", stdin);
	// freopen("", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(); cout.tie();
	cout << setprecision(9);
}

#define int long long
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second

void solve() {
	int n; cin >> n;
	int a[n + 2], b[n + 1];
	for (int i = 1; i <= n + 1; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	
	vector<pair<int, int>> p;
	
	for (int i = 1; i <= n + 1; i++) {
		p.push_back({a[i], i});
	}
	
	sort(all(p));
	sort(b + 1, b + n + 1);
	int idx[n + 2];
	
	for (int i = 0; i < n + 1; i++){
		a[i + 1] = p[i].first;
		idx[i + 1] = p[i].second;
	}
	
	int pref[n + 5] = {}, suf[n + 5] = {};
	for (int i = 1; i <= n; i++) pref[i] = max(max(0ll, a[i] - b[i]), pref[i - 1]);
	
	for (int i = n + 1; i > 1; i--){
		suf[i] = max(max(0ll, a[i] - b[i - 1]), suf[i + 1]);
	}
	
	int ans[n + 5] = {};
	
	for (int i = 1; i <= n + 1; i++){
		ans[idx[i]] = max(pref[i - 1], suf[i + 1]);
	}
	
	for (int i = 1; i <= n + 1; i++) cout << ans[i] << ' ';
	cout << endl;
	
	return;
}

signed main() {
    fast_io();
    srand(chrono::steady_clock::now().time_since_epoch().count());
    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
    return 0;
}

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