Submission #1122779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122779		LucaIlie	Just Long Neckties (JOI20_ho_t1)	C++20	100 / 100	158 ms	7704 KiB

ho_t1

#include <bits/stdc++.h>

using namespace std;

struct necktie {
    int len, pos;
};

const int MAX_N = 2e5;
necktie a[MAX_N + 1], b[MAX_N];
int cost[MAX_N + 2], costPref[MAX_N + 1], costSuf[MAX_N + 3];

int main() {
    int n;

    cin >> n;
    for ( int i = 1; i <= n + 1; i++ ) {
        cin >> a[i].len;
        a[i].pos = i;
    }
    for ( int i = 1; i <= n; i++ ) {
        cin >> b[i].len;
        b[i].pos = i;
    }

    sort( a + 1, a + 1 + n + 1, []( necktie a, necktie b ) { return a.len < b.len; } );
    sort( b + 1, b + 1 + n, []( necktie a, necktie b ) { return a.len < b.len; } );

    for ( int i = 1; i <= n; i++ )
        costPref[i] = max( costPref[i - 1], max( a[i].len - b[i].len, 0 ) );
    for ( int i = n + 1; i >= 2; i-- )
        costSuf[i] = max( costSuf[i + 1], max( a[i].len - b[i - 1].len, 0 ) );

    for ( int i = 1; i <= n + 1; i++ )
        cost[a[i].pos] = max( costPref[i - 1], costSuf[i + 1] );

    for ( int i = 1; i <= n + 1; i++ )
        cout << cost[i] << " ";
    cout << "\n";
}

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