Submission #763108

#	Time	Username	Problem	Language	Result	Execution time	Memory
763108		vjudge1	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	237 ms	15804 KiB

ho_t1

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

typedef long long ll;
typedef pair< int, int > ii;
typedef pair< int, ii > iii;
typedef vector< int > vi;
typedef vector< ii > vii;
typedef vector< iii > viii;
typedef vector< vi > vvi;
typedef vector< vii > vvii;
typedef vector< viii > vviii;
#define hdp 1e9+7
#define MAX LLONG_MAX
#define st first
#define nd second

int main(){
	int n; cin >> n;
	vi a(n+1); for(int i=0; i<=n; i++) cin >> a[i];
	vi a0 = a, b(n); for(int i=0; i<n; i++) cin >> b[i];
	sort(a.begin(), a.end()); sort(b.begin(), b.end());
	unordered_map<int, int> idx; for(int i=0; i<=n; i++) idx[a[i]] = i;
	vi 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]);
	}
}

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