Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # include <iostream>
- # include <vector>
- const int32_t MAX = 1000000000;
- using namespace std;
- int main() {
- int32_t n;
- cin >> n;
- vector<int32_t> a(n);
- vector<int32_t> b(n);
- vector<vector<int32_t>> dp(n);
- vector<vector<int32_t>> prev(n);
- vector<vector<pair<int32_t, int32_t>>> count(n);
- for (size_t i = 0; i < n; i++) {
- dp[i].resize(2, MAX);
- count[i].resize(2);
- prev[i].resize(2);
- }
- for (size_t i = 0; i < n; i++) {
- cin >> a[i];
- }
- for (size_t i = 0; i < n; i++) {
- cin >> b[i];
- }
- prev[0][0] = 0;
- prev[0][1] = 0;
- count[0][0].first = 1;
- count[0][0].second = 0;
- count[0][1].first = 0;
- count[0][1].second = 1;
- dp[0][0] = 0;
- dp[0][1] = 0;
- for (size_t i = 0; i < n - 1; i++) {
- if (i % 2 == 0) {
- if (max(dp[i][0], abs(a[i + 1] - a[i])) < dp[i + 1][0]) {
- dp[i + 1][0] = max(dp[i][0], abs(a[i + 1] - a[i]));
- prev[i + 1][0] = 0;
- count[i + 1][0].first = count[i][0].first + 1;
- count[i + 1][0].second = count[i][0].second;
- }
- if (max(dp[i][0], abs(b[i + 1] - a[i])) < dp[i + 1][1]) {
- dp[i + 1][1] = max(dp[i][0], abs(b[i + 1] - a[i]));
- prev[i + 1][1] = 0;
- count[i + 1][1].first = count[i][0].first;
- count[i + 1][1].second = count[i][0].second + 1;
- }
- if (max(dp[i][1], abs(a[i + 1] - b[i])) < dp[i + 1][0]) {
- dp[i + 1][0] = max(dp[i][1], abs(a[i + 1] - b[i]));
- prev[i + 1][0] = 1;
- count[i + 1][0].first = count[i][1].first + 1;
- count[i + 1][0].second = count[i][1].second;
- }
- if (max(dp[i][1], abs(b[i + 1] - b[i])) < dp[i + 1][1]) {
- dp[i + 1][1] = max(dp[i][1], abs(b[i + 1] - b[i]));
- prev[i + 1][1] = 1;
- count[i + 1][1].first = count[i][1].first;
- count[i + 1][1].second = count[i][1].second + 1;
- }
- }
- else {
- int32_t rev = count[i][0].first - count[i][0].second;
- if (rev == 2 || rev == 0) {
- if (max(dp[i][0], abs(b[i + 1] - a[i])) < dp[i + 1][1]) {
- dp[i + 1][1] = max(dp[i][0], abs(b[i + 1] - a[i]));
- prev[i + 1][1] = 0;
- count[i + 1][1].first = count[i][0].first;
- count[i + 1][1].second = count[i][0].second + 1;
- }
- }
- if (rev == -2 || rev == 0) {
- if (max(dp[i][0], abs(a[i + 1] - a[i])) < dp[i + 1][0]) {
- dp[i + 1][0] = max(dp[i][0], abs(a[i + 1] - a[i]));
- prev[i + 1][0] = 0;
- count[i + 1][0].first = count[i][0].first + 1;
- count[i + 1][0].second = count[i][0].second;
- }
- }
- rev = count[i][1].first - count[i][1].second;
- if (rev == 2 || rev == 0) {
- if (max(dp[i][1], abs(b[i + 1] - b[i])) < dp[i + 1][1]) {
- dp[i + 1][1] = max(dp[i][1], abs(b[i + 1] - b[i]));
- prev[i + 1][1] = 1;
- count[i + 1][1].first = count[i][1].first;
- count[i + 1][1].second = count[i][1].second + 1;
- }
- }
- if (rev == -2 || rev == 0) {
- if (max(dp[i][1], abs(a[i + 1] - b[i])) < dp[i + 1][0]) {
- dp[i + 1][0] = max(dp[i][1], abs(a[i + 1] - b[i]));
- prev[i + 1][0] = 1;
- count[i + 1][0].first = count[i][1].first + 1;
- count[i + 1][0].second = count[i][1].second;
- }
- }
- }
- }
- cout << min(dp[n - 1][0], dp[n - 1][1]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement