This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef pair<long long,long long> ii;
const int N = 2e5+5;
ii a[N];
long long b[N];
long long res[N],n;
long long k[N][2],dp[N];
int main()
{
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n;
for (int i=0;i<n+1;i++) {
cin >> a[i].F;
a[i].S = i;
}
sort(a,a+n+1);
for (int i=0;i<n;i++)
cin >> b[i];
sort(b,b+n);
for (int i=n-1;i>=0;i--) {
k[i][0] = a[i].F - b[i];
k[i][1] = a[i+1].F - b[i];
k[i][0] = max(k[i][0],0ll);
k[i][1] = max(k[i][1],0ll);
// cout << k[i][1] << " ";
}
//cout << endl;
dp[0] = k[0][0];
for (int i=1;i<n;i++) dp[i] = max(dp[i-1],k[i][0]);
res[a[n].S] = dp[n-1];
long long s = 0;
for (int i=n-1;i>=0;i--) {
s = max(s,k[i][1]);
res[a[i].S] = s;
if (i>0) res[a[i].S] = max(res[a[i].S],dp[i-1]);
// cout <<s << " ";
}
for (int i=0;i<=n;i++) cout << res[i] << " ";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |