Submission #568115

#	Time	Username	Problem	Language	Result	Execution time	Memory
568115		MateGiorbelidze	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	124 ms	11656 KiB

ho_t1

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ff first
#define sc second
#define pb push_back
#define in insert


int32_t main () {
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll o = 1; //cin>>o;
    
    while (o--) {
    	
    	ll n; cin>>n;
    	
    	vector<ll> b(n + 1);
    	vector<pair<ll,ll>> a(n + 2);
    	
    	a[0].ff = 0; b[0] = 0;
    	for (int i = 1; i <= n + 1; i++){
    		cin>>a[i].ff;
    		a[i].sc = i;
		}
    		
    	for(int i = 1; i <= n; i++)
    		cin>>b[i];
    	
    	
    	sort(a.begin(),a.end());
    	sort(b.begin(),b.end());
    	
		vector<ll> p(n + 1),s(n + 2);
		p[0] = 0; s[n + 1] = 0;	
		
    	for (int i = 1; i <= n; i++) {
    		
    		p[i] = max(p[i - 1] , (a[i].ff - b[i]));
    		//cout<<p[i]<<" ";
    		
		}
		
		for (int i = n; i > 0; i--) {
			
			s[i] = max(s[i + 1] , (a[i + 1].ff - b[i]));
			//cout<<s[i]<<" ";
			
		}
		
		vector<ll> ans(n + 2);
		for (int i = 1; i <= n + 1; i++) {
			
			ans[a[i].sc] = max(p[i - 1],s[i]);
			
		}	
		
		for (int i = 1; i <= n + 1; i++) {
			
			cout<<ans[i]<<" ";
			
		}
    	
	}
    
}

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