DCOWS - Dancing Cows
It's the spring dance and, in a rare occurrence, the N (1 ≤ N ≤ 5000) bulls have been invited to dance with the M (N < M ≤ 5000) cows (as long as they stay on their very best behavior).
Farmer John, almost obsessive-compulsive in his organization of dances, wants the spectacle to be as visually attractive as possible. Thus, he wants to pair up the N bulls with cow partners such that the total of all the magnitudes of differences in height is minimized. Bulls have heights B_i (1 ≤ B_i ≤ 1,000,000) and cows have height C_i (1 ≤ C_i ≤ 1,000,000). Of course, some cows will be unmatched since N-M of them will have no partners; ignore their heights.
* Line 1: Two space-separated integers: N and M.
* Lines 2..N+1: Line i+1 contains a single integer: B_i.
* Lines N+2..M+N+1: Line i+N+1 contains a single integer: C_i.
* Line 1: A single integer that is the minimum of the sum of the absolute value of the height differences that can be achieved.
SAMPLE INPUT :
5 7 10 16 12 10 13 7 17 12 10 9 6 11
SAMPLE OUTPUT :
Five bulls + seven cows with various heights: Bulls: 10 10 12 13 16 Cows: 6 7 9 10 11 12 17
OUTPUT DETAILS :
Here is one way to achieve a total difference of 4: Bulls: 10 10 12 13 16 Cows: 6 7 9 10 11 12 17
pretty simple.Just a lot of WA due to limiting value. try something in the order of 10^12
Do you have to consider the case N>M ?
@awesome_me the possible answer can be as large as 5000*10^6, so make sure your limiting variable is at least that big.
Those getting wa also check for the case when n = m :)
make sure you are taking min variable long enough to handle all values in dp array(hint for those who are getting WA on test case 15)
Somehow my assert (m > n) failed, but never mind, got Accepted with O(n^2). Does not look like Gold problem at all, hmm...
take dp array as long long int!!
@theph0enix : Greedy approach will not work when a bull has two choices of pairing with same height difference on different sides. i.e a Bull of height H has a choice to pair with two cows of height H-d and H+d . You will never know which choice will give you optimal solution.
Why doesn't the greedy approach work here?
getting wrong ans after or on case 15. Tried using long and scanf and without scanf as well. Simple O(m*n) approach. Somebody please help.
|Cluster:||Cube (Intel G860)|
|Languages:||All except: ADA95 ASM32 ASM64 GAWK BASH BF CLPS CLOJURE LISP clisp LISP sbcl D ERL FSHARP GO ICON ICK LUA NEM NICE NODEJS OCAML PERL6 PIKE PRLG-swi SCALA SCM guile SCM qobi SED ST TCL WHITESPACE|
|Resource:||USACO 2008 Gold|