Submission #951129

#	Time	Username	Problem	Language	Result	Execution time	Memory
951129		star	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	83 ms	14888 KiB

ho_t1

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int n;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;

    vector<pair<LL,int>> a(n+1);
    vector<LL> b(n);
    for (int i=0; i<n+1; i++)
    {
        cin >> a[i].first;
        a[i].second = i;
    }
    for (int i=0; i<n; i++)
        cin >> b[i];

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    vector<LL> left(n+1, 0), right(n+1, 0);

    for (int i=0; i<n; i++)
    {
        left[i+1] = max(left[i], max(a[i].first-b[i], 0LL));
        right[i+1] = max(right[i], max(a[n-i].first-b[n-i-1], 0LL));
    }

    vector<int> res(n+1);

    for (int i=0; i<n+1; i++)
    {
        int id = a[i].second;
        res[id] = max(left[i], right[n-i]);
    }
    for (int i = 0; i < n+1; i++)
    {
        if (i) cout << " ";
        cout << res[i];
    }
    return 0;
}

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