Submission #963808

#	Time	Username	Problem	Language	Result	Execution time	Memory
963808		RaresFelix	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	84 ms	10908 KiB

ho_t1

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")

#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ld = long double;  // or double, if TL is tight
using str = string; 
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;


int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    vi B(n);
    vector<pair<int, int> > A(n + 1);
    for(int i = 0; i <= n; ++i) {
        cin >> A[i].first;
        A[i].second = i;
    }
    for(int i = 0; i < n; ++i) {
        cin >> B[i];
    }
    sort(all(A));
    sort(all(B));
    vi DP1(n), DP2(n);
    for(int i = 0; i < n; ++i) {
        DP1[i] = max(0, -B[i] + A[i].first);
        if(i) DP1[i] = max(DP1[i - 1], DP1[i]);
    }
    for(int i = n - 1; i >= 0; --i) {
        DP2[i] = max(0, -B[i] + A[i + 1].first);
        if(i + 1 < n) DP2[i] = max(DP2[i + 1], DP2[i]);
    }
    vi Re(n + 1, 0);
    for(int i = 0; i <= n; ++i) {
        int v = 0;
        if(i) v = DP1[i - 1];
        if(i < n) v = max(v, DP2[i]);
        Re[A[i].second] = v;
    }
    for(auto it : Re)
        cout << it << " ";
    cout << "\n";

    return 0;
}

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