Submission #879098

#	Time	Username	Problem	Language	Result	Execution time	Memory
879098		frostray8653	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	103 ms	15548 KiB

ho_t1

#include <bits/stdc++.h>
#define int long long
#define IO ios::sync_with_stdio(0), cin.tie(0)
#define FOR(i, a, b) for (int i = a, I = b; i <= I; i++)
using namespace std;
using pii = pair<int, int>;
void dbg() {;}
template<class T, class ...U>
void dbg(T a, U ...b) { cout << a << " "; dbg(b...); }
void ent() { cout << "\n"; }

const int N = 200005;
pii a[N];
int b[N];
int dp_f[N], dp_b[N];
int ans[N];

signed main() {
    IO;

    int n;
    cin >> n;
    FOR(i, 1, n + 1) {
        cin >> a[i].first;
        a[i].second = i;
    }
    FOR(i, 1, n) cin >> b[i];
    sort(a + 1, a + (n + 1) + 1);
    sort(b + 1, b + n + 1);

    for (int i = 1; i <= n; i++)
        dp_f[i] = max(dp_f[i - 1], a[i].first - b[i]);
    for (int i = n + 1; i >= 2; i--)
        dp_b[i] = max(dp_b[i + 1], a[i].first - b[i - 1]);
    for (int i = 1; i <= n + 1; i++) {
        int res = max(dp_f[i - 1], dp_b[i + 1]);
        ans[a[i].second] = res;
    }
    for (int i = 1; i <= n + 1; i++)
        cout << ans[i] << " \n"[i == n + 1];

    return 0;
}

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