제출 #1310742

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310742		qrn	Just Long Neckties (JOI20_ho_t1)	C++20	100 / 100	68 ms	11796 KiB

ho_t1

#include "bits/stdc++.h"
using namespace std;
#define intt long long
#define fi first
#define se second
#define endl "\n"

const intt mxN = 2e5+67;
const intt LG = 20;
const intt inf = 1e18; 
const intt mod = 1e9 + 7;
const intt p = 997;

vector<pair<intt,intt>> a(mxN);
vector<intt> b(mxN);
intt n;

void smile() {
    cin >> n;

    a.resize(n+1);
    b.resize(n);
    for(intt i = 0; i <= n; i++) {
        cin >> a[i].fi;
        a[i].se = i;
    }
    for(intt i = 0; i < n; i++) cin >> b[i];
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    vector<intt> pref(n+2,0ll), suf(n+1,0ll);
    pref[0] = max(0ll, a[0].fi - b[0]);
    for(intt i = 1; i < n; i++) {
        pref[i] = max(pref[i-1], a[i].fi - b[i]);
    }
    pref[n]=pref[n-1];
    suf[n-1] = max(0ll, a[n].fi - b[n-1]);
    for(intt i = n - 2; i >= 0; i--) {
        suf[i] = max(suf[i+1], a[i+1].fi - b[i]);
    }

    vector<intt> ans(n + 2);
    for(intt i = 0; i <= n; i++) {
        intt anss = 0;
        if(i == 0) anss = max(anss, suf[i]);
        else if(i == n) anss = max(anss, pref[i]);
        else anss = max(anss, max(pref[i-1], suf[i]));
        ans[a[i].se] = anss;
    }
    for(intt i = 0; i <= n; i++) {
        cout << ans[i] << " ";
    }
    cout << endl;

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

    // freopen("island.in", "r", stdin);
    // freopen("island.out", "w", stdout)

    intt t = 1, buu = 1;
    // cin >> t;
    while(t--){
        // cout << endl;
        // cout << "Case #" << buu++ << ": ";
        smile();
    }
}

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