Submission #1238417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238417		trimkus	Just Long Neckties (JOI20_ho_t1)	C++20	100 / 100	62 ms	6984 KiB

ho_t1

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




int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<pair<int, int>> a(N + 1);
    vector<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(begin(a), end(a));
    sort(begin(b), end(b));
    vector<int> ps(N + 2), sf(N + 2);
	for (int i = 0; i < N; ++i) {
		ps[i] = max(0, a[i].first - b[i]);
		if (i > 0) {
			ps[i] = max(ps[i - 1], ps[i]);
		}
	}
	// for (int i = 0; i < N; ++i) {
		// cout << ps[i] << " ";
	// }
	// cout << "\n";
	// for (auto& u : a) {
		// cout << u.first << " ";
	// }
	// cout << "\n";
	// for (auto& u : b) {
		// cout << u << " ";
	// }
	// cout << "\n";
	for (int i = N - 1; i >= 0; --i) {
		sf[i] = max(0, a[i + 1].first - b[i]);
		sf[i] = max(sf[i + 1], sf[i]);
	}
	vector<int> res(N + 1);
	for (int i = 0; i < N + 1; ++i) {
		int j = a[i].second;
		int now = sf[i];
		if (i > 0) now = max(now, ps[i - 1]);
		res[j] = now;
	}
	for (int i = 0; i < N + 1; ++i) {
		cout << res[i] << " ";
	}
}

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