题解

#include <unistd.h>

static char inBuf[1 << 16];
static int inLen = 0, inPos = 0;

inline int readChar() {
if (inPos == inLen) {
inLen = read(0, inBuf, sizeof(inBuf));
inPos = 0;
if (inLen <= 0) return -1;
}
return inBuf[inPos++];
}

inline int readInt() {
int c = readChar();
while (c <= ' ') { if (c == -1) return 0; c = readChar(); }
int x = 0;
while (c > ' ') { x = x * 10 + (c - '0'); c = readChar(); }
return x;
}

static int c[305], a[305];
static int dp[305][305];

int main() {
int n = readInt();
for (int i = 1; i <= n; i++) c[i] = readInt();
for (int i = 1; i <= n; i++) a[i] = readInt();

for (int i = 2; i <= n; i++) {
    int key = c[i];
    int j = i - 1;
    while (j >= 1 && c[j] > key) {
        c[j+1] = c[j];
        j--;
    }
    c[j+1] = key;
}

static int diff[305];
for (int j = 1; j <= n; j++) diff[j] = c[n-j+1] - c[j];

for (int i = n; i >= 2; i--) {
    int ai = a[i];
    for (int j = 1; j <= n; j++) {
        int add = ai + diff[j];
        int* dpp = dp[j] + i;
        int* dpprev = dp[j-1];
        for (int k = i; k <= n; k++) {
            int val = dpprev[k-i] + add;
            if (val > dpp[k-i]) dpp[k-i] = val;
        }
    }
}

{
    int ai = a[1];
    for (int j = 1; j <= n; j++) {
        int* dpp = dp[j];
        int* dpprev = dp[j-1];
        for (int k = 1; k <= n; k++) {
            int val = dpprev[k-1] + ai;
            if (val > dpp[k]) dpp[k] = val;
        }
    }
}

int ans = 0;
for (int j = 1; j <= n; j++)
    if (dp[j][n] > ans) ans = dp[j][n];

char out[32];
int len = 0;
if (ans == 0) out[len++] = '0';
else {
    char tmp[24]; int tl = 0;
    while (ans) { tmp[tl++] = '0' + ans % 10; ans /= 10; }
    while (tl) out[len++] = tmp[--tl];
}
out[len++] = '\n';
write(1, out, len);
return 0;

}