Submission #687719

#	Time	Username	Problem	Language	Result	Execution time	Memory
687719		coldy	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	189 ms	10792 KiB

ho_t1

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int n;
    cin>>n;
    pair <int, int> a[n + 1];
    int b[n];
    for(int i = 0; i <= n; i++)cin>>a[i].first, a[i].second = i + 1;
    for(int i = 0; i < n; i++)cin>>b[i];
    sort(a, a + n + 1);
    sort(b, b + n);
    int leftMax[n + 1];
    int rightMax[n + 1];
    int ans[n + 1];
    for(int i = 0; i <= n; i++)ans[i] = (int)1e9;
    for(int i = 0; i <= n; i++)leftMax[i] = 0, rightMax[i] = 0;
    leftMax[0] = (int)0;
    leftMax[1] = max(a[0].first - b[0], 0);
    rightMax[n - 1] = a[n].first - b[n - 1];
    rightMax[n] = (int)0;
    for(int i = 2; i <= n; i++){
        int cur = max(a[i - 1].first - b[i - 1], 0);
        leftMax[i] = max(leftMax[i - 1], cur);
    }
    for(int i = n - 2; i >= 0; i--){
        int cur = max(a[i + 1].first - b[i], 0);
        rightMax[i] = max(rightMax[i + 1], cur);
    }
    for(int i = 0; i <= n; i++){
        //cout<<leftMax[i]<<" "<<rightMax[i]<<endl;
        ans[a[i].second - 1] = max(leftMax[i], rightMax[i]);
    }
    for(int i = 0; i <= n; i++)cout<<ans[i]<<" ";
}

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