This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
数列が与えられる．各要素の中で$2$つ選びペアを作っても良い．ペアの場合は要素同士の積を取った後に，すべての(ペアを作っていないものも足して)和を最大化したい．
全てが正の数だった場合，大きいものから順番にペアを作っていけばよい．負の数がある場合，絶対値が大きいものから負の数同士でペアを作っていくのがよい．後はペアを作れない負の数があった場合，そのまま足してしまうと和の合計は下がってしまうので，もし$0$があれば，それで消す．
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
class CreatePairs {
public :
int maximalSum ( vector < int > data ) {
int cnt = 0 ;
ll sum = 0 ;
priority_queue < int > up ;
priority_queue < int , vector < int > , greater < int > > down ;
rep ( i , data . size ()) {
if ( data [ i ] == 0 ) cnt ++ ;
if ( data [ i ] == 1 ) {
sum ++ ;
continue ;
}
if ( data [ i ] < 0 ) down . push ( data [ i ]);
if ( 0 < data [ i ]) up . push ( data [ i ]);
}
while ( up . size ()) {
if ( up . size () >= 2 ) {
int a = up . top (); up . pop ();
int b = up . top (); up . pop ();
sum += a * b ;
} else {
sum += up . top (); up . pop ();
}
}
while ( down . size ()) {
if ( down . size () >= 2 ) {
int a = down . top (); down . pop ();
int b = down . top (); down . pop ();
sum += a * b ;
} else {
int a = down . top (); down . pop ();
if ( cnt ) cnt -- ;
else sum += a ;
}
}
return sum ;
}
};