Submission #217415

#	Time	Username	Problem	Language	Result	Execution time	Memory
217415		AMO5	Just Long Neckties (JOI20_ho_t1)	C++98	100 / 100	131 ms	20448 KiB

ho_t1

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

ll INF=LLONG_MAX;

ll b[200222],c[200222],cnt[200222],cnt2[200222],dp[200222],dp2[200222],ans[200222];
vector < pll > a;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	int n; cin >> n;
	for(int i=0; i<=n; i++){
		cin >> c[i]; 
		a.pb({c[i],i});
		cnt[i]=0; dp[i]=0;
		cnt2[i]=0; dp2[i]=0;
	}
	for(int i=0; i<n; i++)cin >> b[i];
	sort(b,b+n);
	sort(a.begin(),a.end());
	for(int i=0; i<n; i++){
		cnt[i] = max(a[i].fi-b[i],(ll)0);
		cnt2[i] = max(a[i+1].fi-b[i],(ll)0);
	}
	dp[0]=cnt[0];
	for(int i=1; i<=n; i++){	
		dp[i] = max(dp[i-1],cnt[i]);
	}
	for(int i=n-1; i>=0; i--){
		dp2[i] = max(dp2[i+1],cnt2[i]);
	}
	for(int i=0; i<=n; i++){
		ans[a[i].se]=max(dp[i],dp2[i]);
	}
	for(int i=0; i<=n; i++)cout << ans[i] << ' ';
	cout << endl;	
}	

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