Submission #762986

#	Time	Username	Problem	Language	Result	Execution time	Memory
762986		vjudge1	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	291 ms	15528 KiB

ho_t1

#include <bits/stdc++.h>
using namespace std;
main()
{
	int n; cin >> n;
	vector <int> a(n + 1);
	for(int i = 0; i <= n; i++) cin >> a[i];
	vector <int> a0 = a;
	vector <int> b(n);
	for(int i = 0; i < n; i++) cin >> b[i];
	sort(a.begin(), a.end()); sort(b.begin(), b.end());
	map <int, int> idx;
	for(int i = 0; i <= n; i++) idx[a[i]] = i;
	vector <int> dpl(n + 1), dpr(n + 1);
	for(int i = 1; i <= n; i++)
	{
		dpl[i] = max(0, a[i - 1] - b[i - 1]);
		dpr[i - 1] = max(0, a[i] - b[i - 1]);
	}
	for(int i = 1; i <= n; i++) dpl[i] = max(dpl[i], dpl[i - 1]);
	for(int i = n; i >= 1; i--) dpr[i - 1] = max(dpr[i - 1], dpr[i]);
	for(int i = 0; i <= n; i++)
	{
		if(i != 0) cout << " ";
		int trace = idx[a0[i]];
		cout << max(dpl[trace], dpr[trace]);
	}
}

Compilation message (stderr)

ho_t1.cpp:3:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    3 | main()
      | ^~~~

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