Submission #719093

#	Time	Username	Problem	Language	Result	Execution time	Memory
719093		thimote75	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	113 ms	10820 KiB

ho_t1

#include <bits/stdc++.h>

using namespace std;

#define di pair<int, int>

int nbTypes;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> nbTypes;    
    vector<di> a(nbTypes + 1);
    for (int iT = 0; iT <= nbTypes; iT ++) {
        int x;
        cin >> x;

        a[iT] = { x, iT };
    }
    vector<int> b(nbTypes);
    for (int jT = 0; jT < nbTypes; jT ++)
        cin >> b[jT];
    
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    vector<int> c(nbTypes + 1);
    vector<int> d(nbTypes + 1);
    for (int iT = 0; iT < nbTypes; iT ++) {
        c[iT]     = a[iT].first - b[iT];
        d[iT + 1] = a[iT + 1].first - b[iT];
    }

    for (int iT = 1; iT <= nbTypes; iT ++)
        c[iT] = max(c[iT], c[iT - 1]);
    for (int jT = nbTypes - 1; jT >= 0; jT --)
        d[jT] = max(d[jT + 1], d[jT]);
    
    vector<int> res (nbTypes + 1);
    for (int i = 0; i <= nbTypes; i ++) {
        int mu = i == 0 ? 0 : c[i - 1];
        int nu = i == nbTypes ? 0 : d[i + 1];

        res[a[i].second] = max(mu, nu);
    }

    for (int u : res)
        cout << u << " ";
}

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