Two Sequences
Time limit2sMemory limit128 MB
Partition two sequences from the back into matched groups to minimize the total sum of products of adjusted group sums, requiring an optimized DP over prefix sums.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Prefix sum, Math
- Solved
- No attempts yet
Problem
You are given a sequence A of length N and a sequence B of length M. Every element is a positive integer. A game is played with these two sequences.
In one step, choose K1 elements (K1 >= 1) from the end of the current sequence A, and choose K2 elements (K2 >= 1) from the end of the current sequence B. Let S1 be the sum of the chosen elements from A, and let S2 be the sum of the chosen elements from B. The score for this step is (S1 - K1) x (S2 - K2). Then remove the chosen elements from their sequences.
Repeat this process until all elements of both sequences have been removed. The total score is the sum of the scores from all steps.
Each step must remove at least one element from each sequence. Therefore, it is not allowed for one sequence to become empty while the other sequence still has elements remaining.
Given the two sequences, find the minimum possible total score.
Input
The first line contains two integers N and M (1 <= N, M <= 2,000).
The second line contains the elements of sequence A in order from front to back.
The third line contains the elements of sequence B in order from front to back.
All elements of both sequences are positive integers not greater than 1,000.
Output
Print the minimum possible total score on the first line.