Submission #418028

#TimeUsernameProblemLanguageResultExecution timeMemory
418028ChaskaJust Long Neckties (JOI20_ho_t1)C++11
100 / 100
123 ms17096 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...