Algorithm

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from input/code.cpp:1:
input/code.cpp: In function 'long int ftest(std::vector<long int>&, std::vector<long int>&, int)':
input/code.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert( a.size() == n );
           ~~~~~~~~~^~~~
input/code.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert( b.size() == n );
           ~~~~~~~~~^~~~
input/code.cpp:78:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<aod.size(); i++) {
                 ~^~~~~~~~~~~
input/code.cpp:81:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<aev.size(); i++) {
                 ~^~~~~~~~~~~

#include <bits/stdc++.h>

using namespace std;

typedef bitset<20> bs;
typedef int64_t ll;
typedef pair<ll,ll> PLL;
typedef pair<int, pair<int,int>> PQ;

// [a][b][t] start a end b start at time t
  int vals[100][100][501];


long f(int i, int j, vector<ll> & a, vector<ll> & b, int n) {
  if (i >= n) return 0;
  swap(a[i],a[j]);
  long r = a[i]*b[i] + f(i+1,i+1,b,a,n);
  swap(a[i],a[j]);

    
  if (j < n-2) {
    r = min(r, f(i,j+2,a,b,n));
  }
  return r;
}




int INF = 1<<30;
long fn(int i, int j, vector<ll> & a, vector<ll> & b, int n) {
  if (i >= n) return 0;

  swap(a[i],a[j]);
  long r = a[i]*b[i] + f(i+1,i+1,b,a,n);
  swap(a[i],a[j]);

  if (j==i) {
    for (j=i+2; j<n-2; j+=2) {
      swap(a[i],a[j]);
      r = min(r, a[i]*b[i] + f(i+1,i+1,b,a,n));
      swap(a[i],a[j]);
    }
  }

  return r;
}

long ftest(vector<ll> & a, vector<ll> & b, int n) {

  vector<ll> aev;
  vector<ll>  bev;
  vector<ll>  aod;
  vector<ll>  bod;

  assert( a.size() == n );
  assert( b.size() == n );
  
  for (int i=0; i<n; i++) {
    if (i&1) {
      //cout << i << " " << a.size() << endl;
      //cout << a[i] << " " << b[i] << endl;
      aod.push_back(a[i]);
      bod.push_back(b[i]);
    } else {
      aev.push_back(a[i]);
      bev.push_back(b[i]);
    }
  }

  sort(aod.begin(), aod.end());
  sort(bod.begin(), bod.end(), greater<ll>());
  sort(aev.begin(), aev.end());
  sort(bev.begin(), bev.end(), greater<ll>());

  ll res = 0;

  for (int i=0; i<aod.size(); i++) {
    res += aod[i] * bod[i];
  }
  for (int i=0; i<aev.size(); i++) {
    res += aev[i] * bev[i];
  }

  return res;
}


int main() {

  cout << std::setprecision(15);

  int n;
  cin >> n;

  vector<ll> a (n);
  vector<ll> b(n);
  for (int ai=0; ai<n; ai++) {
    cin >> a[ai];
  }
  for (int ai=0; ai<n; ai++) {
    cin >> b[ai];
  }

  //  cout << fn(0,0,a,b,n) << endl;;
  cout << ftest(a,b,n) << endl;;
  
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED