# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
635624 | aris12345678 | Just Long Neckties (JOI20_ho_t1) | C++14 | 115 ms | 11064 KiB |
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>
using namespace std;
typedef pair<int, int> pii;
#define X first
#define Y second
int main() {
int n;
scanf("%d", &n);
vector<pii> a(n+1);
vector<int> b(n);
for(int i = 0; i <= n; i++) {
scanf("%d", &a[i].X);
a[i].Y = i;
}
for(int i = 0; i < n; i++)
scanf("%d", &b[i]);
sort(a.begin(), a.end());
sort(b.begin(), b.end());
vector<int> pref;
pref.push_back(max(a[0].X-b[0], 0));
for(int i = 1; i < n; i++)
pref.push_back(max(pref.back(), a[i].X-b[i]));
// for(int i = 0; i < n; i++)
// printf("%d ", pref[i]);
// printf("\n");
vector<int> suf;
suf.push_back(max(a[n].X-b[n-1], 0));
for(int i = n-2; i >= 0; i--)
suf.push_back(max(suf.back(), a[i+1].X-b[i]));
reverse(suf.begin(), suf.end());
// for(int i = 0; i < n; i++)
// printf("%d ", suf[i]);
// printf("\n");
vector<int> ans(n+1);
for(int i = 0; i <= n; i++) {
if(i == 0)
ans[a[i].Y] = suf[i];
else if(i == n)
ans[a[i].Y] = pref[i-1];
else {
ans[a[i].Y] = max(pref[i-1], suf[i]);
// cout << a[i].Y << " " << pref[i-1] << " " << suf[i] << "\n";
}
}
for(int i = 0; i <= n; i++)
printf("%d ", ans[i]);
printf("\n");
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |