1519D - Maximum Sum of Products

SXWisON molingspance

Idea

Assuming the old range is l~r, and expanded it by one unit, we get l-1~r+1,

It's interesting that, we only need calculate the changed portion, that is:

add: a[r+1]*b[l-1] + a[l-1]*b[r+1]

sub: a[l-1]*b[l-1] + a[r+1]*b[r+1]

Implementation

To implement this traversal, consider two scenarios:

when the swapped sequence has an even length, and when the swapped sequence has an odd length.

The indices for these scenarios are as follows:

• Odd length: l-i~r+i
• Even length: l-i+1~r+i

Code

#include <iostream>

typedef long long int LL;

LL a[5010];
LL b[5010];

int main() {
  int n;
  std::cin >> n;
  for (int i = 0;i < n;i++) {
    std::cin >> a[i];
  }
  for (int i = 0;i < n;i++) {
    std::cin >> b[i];
  }
  // Record the maximum value of change
  LL max = 0;
  // case of odd number exchange
  // Traverse Center
  // Note: It is meaningless to exchange only one, so at least three should be exchanged
  for (int i = 1; i < n - 1; i++) {
    LL delta = 0;
    // Exchange radius
    for (int r = 1; i - r >= 0 && i + r < n; r++) {
      delta -= a[i - r] * b[i - r] + a[i + r] * b[i + r];
      delta += a[i - r] * b[i + r] + a[i + r] * b[i - r];
      if (delta > max)
        max = delta;
    }
  }
  // The case of even number exchange
  // The definition is that the index is on the left side
  for (int i = 0; i < n - 1;i++) {
    LL delta = 0;
    // Exchange radius
    for (int r = 1; (i - r + 1) >= 0 && (i + r) < n;r++) {
      delta -= a[i - r + 1] * b[i - r + 1] + a[i + r] * b[i + r];
      delta += a[i - r + 1] * b[i + r] + b[i - r + 1] * a[i + r];
      if (delta > max)
        max = delta;
    }
  }
  // Calculate Total Sum
  LL sum = 0;
  for (int i = 0;i < n;i++) {
    sum += a[i] * b[i];
  }
  std::cout << sum + max;
  return 0;
}