oj.uz

Submission #337270

# Submission time Handle Problem Language Result Execution time Memory
337270 2020-12-19T07:26:33 Z ram Just Long Neckties (JOI20_ho_t1) C++14
0 / 100
 1 ms 364 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

main() {
	int n;
	cin >> n;
	
	pair<int, int> a[n+1];
	int b[n];
	
	for (int i = 0; i < n+1; i++) {
		cin >> a[i].first;
		a[i].second = i;
	}
	
	for (int i = 0; i < n; i++) {
		cin >> b[i];
	}
	
	sort(a, a+n+1);
	sort(b, b+n);
	
	int same[n]; // max( sorted a[i] - sorted b[i] , 0 ) (i goes from 0 to n-1 inclusive)
	int diff[n]; // max( sorted a[i+1] - sorted b[i], 0 ) (i goes from 0 to n-1 inclusive)
	
	for (int i = 0; i < n; i++) {
		same[i] = a[i].first - b[i];
		if (same[i] < 0) same[i] = 0;
		diff[i] = a[i+1].first - b[i];
		if (diff[i] < 0) diff[i] = 0;
	}
	
	int maxsame[n];
	int maxdiff[n];
	
	maxsame[0] = same[0];
	maxdiff[n-1] = diff[n-1];
	
	for (int i = 1; i < n; i++) {
		maxsame[i] = max(maxsame[i-1], same[i]);
	}
	
	for (int i = n-2; i >= 0; i--) {
		maxdiff[i] = max(maxdiff[i+1], diff[i]);
	}
	
	int ans[n+1];
	
	for (int i = 0; i < n+1; i++) {
		int index = a[i].second;
		if (index == 0) {
			ans[index] = maxdiff[index];
		} else if (index == n) {
			ans[index] = maxsame[index-1];
		} else {
			ans[index] = max(maxsame[index-1], maxdiff[index]);
		}
	}
	
	for (int i = 0; i < n+1; i++) {
		cout << ans[i] << " ";
	}
}

Compilation message

ho_t1.cpp:6:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    6 | main() {
      |      ^

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 91.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -