Submission #355554

#	Time	Username	Problem	Language	Result	Execution time	Memory
355554		Jarif_Rahman	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	190 ms	15580 KiB

ho_t1

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    vector<ll> a(n+1), b(n);
    vector<pair<ll, int>> aa;
    for(int i = 0; i <= n; i++){
        ll x; cin >> x;
        a[i] = x;
        aa.pb({x, i});
    }
    for(ll &x: b) cin >> x;
    sort(a.begin(), a.end());
    sort(aa.begin(), aa.end());
    sort(b.begin(), b.end());
    vector<ll> dpa(n, 0), dpb(n, 0);
    dpa[0] = max(a[0]-b[0], 0LL);
    dpb[n-1] = max(a[n] - b[n-1], 0LL);
    for(int i = 1; i < n; i++) dpa[i] = max(dpa[i-1], max(a[i] - b[i], 0LL));
    for(int i = n-2; i >= 0; i--) dpb[i] = max(dpb[i+1], max(a[i+1] - b[i], 0LL));
    for(int i = 0; i <= n; i++){
        aa[i].f = i;
        ll tmp = aa[i].f;
        aa[i].f = aa[i].sc;
        aa[i].sc = tmp;
    }
    sort(aa.begin(), aa.end());
    for(int i = 0; i <= n; i++){
        int in = aa[i].sc;
        ll ans = 0;
        if(in > 0) ans = max(ans, dpa[in-1]);
        if(in < n) ans = max(ans, dpb[in]);
        cout << ans << " ";
    }
    cout << "\n";
}

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