Artifact a01ad9bff4f4fef14182ee26c85923e12d3e22b6:
0000: 23 69 6e 63 6c 75 64 65 20 3c 69 6f 73 74 72 65 #include <iostre
0010: 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 am>..#include <s
0020: 73 74 72 65 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 stream>..#includ
0030: 65 20 3c 69 6f 6d 61 6e 69 70 3e 0d 0a 23 69 6e e <iomanip>..#in
0040: 63 6c 75 64 65 20 3c 76 65 63 74 6f 72 3e 0d 0a clude <vector>..
0050: 23 69 6e 63 6c 75 64 65 20 3c 73 74 72 69 6e 67 #include <string
0060: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 6d 61 70 >..#include <map
0070: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 65 74 >..#include <set
0080: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 61 6c 67 >..#include <alg
0090: 6f 72 69 74 68 6d 3e 0d 0a 23 69 6e 63 6c 75 64 orithm>..#includ
00a0: 65 20 3c 6e 75 6d 65 72 69 63 3e 0d 0a 23 69 6e e <numeric>..#in
00b0: 63 6c 75 64 65 20 3c 69 74 65 72 61 74 6f 72 3e clude <iterator>
00c0: 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 66 75 6e 63 ..#include <func
00d0: 74 69 6f 6e 61 6c 3e 0d 0a 23 69 6e 63 6c 75 64 tional>..#includ
00e0: 65 20 3c 63 6f 6d 70 6c 65 78 3e 0d 0a 23 69 6e e <complex>..#in
00f0: 63 6c 75 64 65 20 3c 71 75 65 75 65 3e 0d 0a 23 clude <queue>..#
0100: 69 6e 63 6c 75 64 65 20 3c 73 74 61 63 6b 3e 0d include <stack>.
0110: 0a 23 69 6e 63 6c 75 64 65 20 3c 63 6d 61 74 68 .#include <cmath
0120: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 61 73 >..#include <cas
0130: 73 65 72 74 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 sert>..#include
0140: 3c 63 73 74 72 69 6e 67 3e 0d 0a 23 69 66 64 65 <cstring>..#ifde
0150: 66 20 5f 5f 47 4e 55 43 5f 5f 0d 0a 23 69 6e 63 f __GNUC__..#inc
0160: 6c 75 64 65 20 3c 65 78 74 2f 68 61 73 68 5f 6d lude <ext/hash_m
0170: 61 70 3e 0d 0a 23 64 65 66 69 6e 65 20 75 6e 6f ap>..#define uno
0180: 72 64 65 72 65 64 5f 6d 61 70 20 5f 5f 67 6e 75 rdered_map __gnu
0190: 5f 63 78 78 3a 3a 68 61 73 68 5f 6d 61 70 0d 0a _cxx::hash_map..
01a0: 23 65 6c 73 65 0d 0a 23 69 6e 63 6c 75 64 65 20 #else..#include
01b0: 3c 75 6e 6f 72 64 65 72 65 64 5f 6d 61 70 3e 0d <unordered_map>.
01c0: 0a 23 65 6e 64 69 66 0d 0a 75 73 69 6e 67 20 6e .#endif..using n
01d0: 61 6d 65 73 70 61 63 65 20 73 74 64 3b 0d 0a 74 amespace std;..t
01e0: 79 70 65 64 65 66 20 6c 6f 6e 67 20 6c 6f 6e 67 ypedef long long
01f0: 20 4c 4c 3b 0d 0a 74 79 70 65 64 65 66 20 63 6f LL;..typedef co
0200: 6d 70 6c 65 78 3c 64 6f 75 62 6c 65 3e 20 43 4d mplex<double> CM
0210: 50 3b 0d 0a 0d 0a 63 6c 61 73 73 20 4d 65 72 67 P;....class Merg
0220: 65 72 73 44 69 76 4f 6e 65 20 7b 20 70 75 62 6c ersDivOne { publ
0230: 69 63 3a 0d 0a 09 64 6f 75 62 6c 65 20 66 69 6e ic:...double fin
0240: 64 4d 61 78 69 6d 75 6d 28 76 65 63 74 6f 72 20 dMaximum(vector
0250: 3c 69 6e 74 3e 20 72 65 76 65 6e 75 65 73 29 0d <int> revenues).
0260: 0a 09 7b 0d 0a 09 09 76 65 63 74 6f 72 3c 64 6f ..{....vector<do
0270: 75 62 6c 65 3e 20 72 28 72 65 76 65 6e 75 65 73 uble> r(revenues
0280: 2e 62 65 67 69 6e 28 29 2c 20 72 65 76 65 6e 75 .begin(), revenu
0290: 65 73 2e 65 6e 64 28 29 29 3b 0d 0a 09 09 73 6f es.end());....so
02a0: 72 74 28 72 2e 62 65 67 69 6e 28 29 2c 20 72 2e rt(r.begin(), r.
02b0: 65 6e 64 28 29 29 3b 0d 0a 09 09 72 65 74 75 72 end());....retur
02c0: 6e 20 62 65 73 74 28 72 2c 20 72 2e 73 69 7a 65 n best(r, r.size
02d0: 28 29 29 3b 0d 0a 09 7d 0d 0a 0d 0a 0d 0a 09 6d ());...}.......m
02e0: 61 70 3c 69 6e 74 2c 20 64 6f 75 62 6c 65 3e 20 ap<int, double>
02f0: 6d 65 6d 6f 3b 0d 0a 09 64 6f 75 62 6c 65 20 62 memo;...double b
0300: 65 73 74 28 63 6f 6e 73 74 20 76 65 63 74 6f 72 est(const vector
0310: 3c 64 6f 75 62 6c 65 3e 26 20 72 2c 20 69 6e 74 <double>& r, int
0320: 20 4e 29 0d 0a 09 7b 0d 0a 09 09 69 66 28 20 4e N)...{....if( N
0330: 20 3d 3d 20 31 20 29 0d 0a 09 09 09 72 65 74 75 == 1 ).....retu
0340: 72 6e 20 72 5b 30 5d 3b 0d 0a 09 09 69 66 28 20 rn r[0];....if(
0350: 6d 65 6d 6f 2e 63 6f 75 6e 74 28 4e 29 20 29 20 memo.count(N) )
0360: 0d 0a 09 09 09 72 65 74 75 72 6e 20 6d 65 6d 6f .....return memo
0370: 5b 4e 5d 3b 0d 0a 0d 0a 09 09 64 6f 75 62 6c 65 [N];......double
0380: 20 73 63 6f 72 65 20 3d 20 2d 31 65 2b 31 30 30 score = -1e+100
0390: 3b 0d 0a 09 09 66 6f 72 28 69 6e 74 20 6b 3d 31 ;....for(int k=1
03a0: 3b 20 6b 3c 4e 3b 20 2b 2b 6b 29 20 7b 0d 0a 09 ; k<N; ++k) {...
03b0: 09 09 64 6f 75 62 6c 65 20 61 20 3d 20 61 63 63 ..double a = acc
03c0: 75 6d 75 6c 61 74 65 28 72 2e 62 65 67 69 6e 28 umulate(r.begin(
03d0: 29 2b 6b 2c 20 72 2e 62 65 67 69 6e 28 29 2b 4e )+k, r.begin()+N
03e0: 2c 20 62 65 73 74 28 72 2c 20 6b 29 29 20 2f 20 , best(r, k)) /
03f0: 28 4e 2d 6b 2b 31 29 3b 0d 0a 09 09 09 73 63 6f (N-k+1);.....sco
0400: 72 65 20 3d 20 6d 61 78 28 73 63 6f 72 65 2c 20 re = max(score,
0410: 61 29 3b 0d 0a 09 09 7d 0d 0a 09 09 72 65 74 75 a);....}....retu
0420: 72 6e 20 6d 65 6d 6f 5b 4e 5d 20 3d 20 73 63 6f rn memo[N] = sco
0430: 72 65 3b 0d 0a 09 7d 0d 0a 7d 3b 0d 0a 0d 0a 2f re;...}..};..../
0440: 2f 20 42 45 47 49 4e 20 43 55 54 20 48 45 52 45 / BEGIN CUT HERE
0450: 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 74 69 6d ..#include <ctim
0460: 65 3e 0d 0a 64 6f 75 62 6c 65 20 73 74 61 72 74 e>..double start
0470: 5f 74 69 6d 65 3b 20 73 74 72 69 6e 67 20 74 69 _time; string ti
0480: 6d 65 72 28 29 0d 0a 20 7b 20 6f 73 74 72 69 6e mer().. { ostrin
0490: 67 73 74 72 65 61 6d 20 6f 73 3b 20 6f 73 20 3c gstream os; os <
04a0: 3c 20 22 20 28 22 20 3c 3c 20 69 6e 74 28 28 63 < " (" << int((c
04b0: 6c 6f 63 6b 28 29 2d 73 74 61 72 74 5f 74 69 6d lock()-start_tim
04c0: 65 29 2f 43 4c 4f 43 4b 53 5f 50 45 52 5f 53 45 e)/CLOCKS_PER_SE
04d0: 43 2a 31 30 30 30 29 20 3c 3c 20 22 20 6d 73 65 C*1000) << " mse
04e0: 63 29 22 3b 20 72 65 74 75 72 6e 20 6f 73 2e 73 c)"; return os.s
04f0: 74 72 28 29 3b 20 7d 0d 0a 74 65 6d 70 6c 61 74 tr(); }..templat
0500: 65 3c 74 79 70 65 6e 61 6d 65 20 54 3e 20 6f 73 e<typename T> os
0510: 74 72 65 61 6d 26 20 6f 70 65 72 61 74 6f 72 3c tream& operator<
0520: 3c 28 6f 73 74 72 65 61 6d 26 20 6f 73 2c 20 63 <(ostream& os, c
0530: 6f 6e 73 74 20 76 65 63 74 6f 72 3c 54 3e 26 20 onst vector<T>&
0540: 76 29 0d 0a 20 7b 20 6f 73 20 3c 3c 20 22 7b 20 v).. { os << "{
0550: 22 3b 0d 0a 20 20 20 66 6f 72 28 74 79 70 65 6e ";.. for(typen
0560: 61 6d 65 20 76 65 63 74 6f 72 3c 54 3e 3a 3a 63 ame vector<T>::c
0570: 6f 6e 73 74 5f 69 74 65 72 61 74 6f 72 20 69 74 onst_iterator it
0580: 3d 76 2e 62 65 67 69 6e 28 29 3b 20 69 74 21 3d =v.begin(); it!=
0590: 76 2e 65 6e 64 28 29 3b 20 2b 2b 69 74 29 0d 0a v.end(); ++it)..
05a0: 20 20 20 6f 73 20 3c 3c 20 27 5c 22 27 20 3c 3c os << '\"' <<
05b0: 20 2a 69 74 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 *it << '\"' <<
05c0: 28 69 74 2b 31 3d 3d 76 2e 65 6e 64 28 29 20 3f (it+1==v.end() ?
05d0: 20 22 22 20 3a 20 22 2c 20 22 29 3b 20 6f 73 20 "" : ", "); os
05e0: 3c 3c 20 22 20 7d 22 3b 20 72 65 74 75 72 6e 20 << " }"; return
05f0: 6f 73 3b 20 7d 0d 0a 76 6f 69 64 20 76 65 72 69 os; }..void veri
0600: 66 79 5f 63 61 73 65 28 63 6f 6e 73 74 20 64 6f fy_case(const do
0610: 75 62 6c 65 26 20 45 78 70 65 63 74 65 64 2c 20 uble& Expected,
0620: 63 6f 6e 73 74 20 64 6f 75 62 6c 65 26 20 52 65 const double& Re
0630: 63 65 69 76 65 64 29 20 7b 0d 0a 20 62 6f 6f 6c ceived) {.. bool
0640: 20 6f 6b 20 3d 20 28 61 62 73 28 45 78 70 65 63 ok = (abs(Expec
0650: 74 65 64 20 2d 20 52 65 63 65 69 76 65 64 29 20 ted - Received)
0660: 3c 20 31 65 2d 39 29 3b 0d 0a 20 69 66 28 6f 6b < 1e-9);.. if(ok
0670: 29 20 63 65 72 72 20 3c 3c 20 22 50 41 53 53 45 ) cerr << "PASSE
0680: 44 22 20 3c 3c 20 74 69 6d 65 72 28 29 20 3c 3c D" << timer() <<
0690: 20 65 6e 64 6c 3b 20 20 65 6c 73 65 20 7b 20 63 endl; else { c
06a0: 65 72 72 20 3c 3c 20 22 46 41 49 4c 45 44 22 20 err << "FAILED"
06b0: 3c 3c 20 74 69 6d 65 72 28 29 20 3c 3c 20 65 6e << timer() << en
06c0: 64 6c 3b 0d 0a 20 63 65 72 72 20 3c 3c 20 22 5c dl;.. cerr << "\
06d0: 74 6f 3a 20 5c 22 22 20 3c 3c 20 45 78 70 65 63 to: \"" << Expec
06e0: 74 65 64 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 65 ted << '\"' << e
06f0: 6e 64 6c 20 3c 3c 20 22 5c 74 78 3a 20 5c 22 22 ndl << "\tx: \""
0700: 20 3c 3c 20 52 65 63 65 69 76 65 64 20 3c 3c 20 << Received <<
0710: 27 5c 22 27 20 3c 3c 20 65 6e 64 6c 3b 20 7d 20 '\"' << endl; }
0720: 7d 0d 0a 23 64 65 66 69 6e 65 20 43 41 53 45 28 }..#define CASE(
0730: 4e 29 20 7b 63 65 72 72 20 3c 3c 20 22 54 65 73 N) {cerr << "Tes
0740: 74 20 43 61 73 65 20 23 22 20 3c 3c 20 4e 20 3c t Case #" << N <
0750: 3c 20 22 2e 2e 2e 22 20 3c 3c 20 66 6c 75 73 68 < "..." << flush
0760: 3b 20 73 74 61 72 74 5f 74 69 6d 65 3d 63 6c 6f ; start_time=clo
0770: 63 6b 28 29 3b 0d 0a 23 64 65 66 69 6e 65 20 45 ck();..#define E
0780: 4e 44 09 20 76 65 72 69 66 79 5f 63 61 73 65 28 ND. verify_case(
0790: 5f 2c 20 4d 65 72 67 65 72 73 44 69 76 4f 6e 65 _, MergersDivOne
07a0: 28 29 2e 66 69 6e 64 4d 61 78 69 6d 75 6d 28 72 ().findMaximum(r
07b0: 65 76 65 6e 75 65 73 29 29 3b 7d 0d 0a 69 6e 74 evenues));}..int
07c0: 20 6d 61 69 6e 28 29 7b 0d 0a 0d 0a 43 41 53 45 main(){....CASE
07d0: 28 30 29 0d 0a 09 69 6e 74 20 72 65 76 65 6e 75 (0)...int revenu
07e0: 65 73 5f 5b 5d 20 3d 20 7b 35 2c 20 2d 37 2c 20 es_[] = {5, -7,
07f0: 33 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 3};... vector <
0800: 69 6e 74 3e 20 72 65 76 65 6e 75 65 73 28 72 65 int> revenues(re
0810: 76 65 6e 75 65 73 5f 2c 20 72 65 76 65 6e 75 65 venues_, revenue
0820: 73 5f 2b 73 69 7a 65 6f 66 28 72 65 76 65 6e 75 s_+sizeof(revenu
0830: 65 73 5f 29 2f 73 69 7a 65 6f 66 28 2a 72 65 76 es_)/sizeof(*rev
0840: 65 6e 75 65 73 5f 29 29 3b 20 0d 0a 09 64 6f 75 enues_)); ...dou
0850: 62 6c 65 20 5f 20 3d 20 31 2e 35 3b 20 0d 0a 45 ble _ = 1.5; ..E
0860: 4e 44 0d 0a 43 41 53 45 28 31 29 0d 0a 09 69 6e ND..CASE(1)...in
0870: 74 20 72 65 76 65 6e 75 65 73 5f 5b 5d 20 3d 20 t revenues_[] =
0880: 7b 31 30 2c 20 2d 31 37 7d 3b 0d 0a 09 20 20 76 {10, -17};... v
0890: 65 63 74 6f 72 20 3c 69 6e 74 3e 20 72 65 76 65 ector <int> reve
08a0: 6e 75 65 73 28 72 65 76 65 6e 75 65 73 5f 2c 20 nues(revenues_,
08b0: 72 65 76 65 6e 75 65 73 5f 2b 73 69 7a 65 6f 66 revenues_+sizeof
08c0: 28 72 65 76 65 6e 75 65 73 5f 29 2f 73 69 7a 65 (revenues_)/size
08d0: 6f 66 28 2a 72 65 76 65 6e 75 65 73 5f 29 29 3b of(*revenues_));
08e0: 20 0d 0a 09 64 6f 75 62 6c 65 20 5f 20 3d 20 2d ...double _ = -
08f0: 33 2e 35 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 3.5; ..END..CASE
0900: 28 32 29 0d 0a 09 69 6e 74 20 72 65 76 65 6e 75 (2)...int revenu
0910: 65 73 5f 5b 5d 20 3d 20 7b 31 32 2c 20 31 32 2c es_[] = {12, 12,
0920: 20 31 32 2c 20 31 32 2c 20 31 32 7d 3b 0d 0a 09 12, 12, 12};...
0930: 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 72 vector <int> r
0940: 65 76 65 6e 75 65 73 28 72 65 76 65 6e 75 65 73 evenues(revenues
0950: 5f 2c 20 72 65 76 65 6e 75 65 73 5f 2b 73 69 7a _, revenues_+siz
0960: 65 6f 66 28 72 65 76 65 6e 75 65 73 5f 29 2f 73 eof(revenues_)/s
0970: 69 7a 65 6f 66 28 2a 72 65 76 65 6e 75 65 73 5f izeof(*revenues_
0980: 29 29 3b 20 0d 0a 09 64 6f 75 62 6c 65 20 5f 20 )); ...double _
0990: 3d 20 31 32 2e 30 3b 20 0d 0a 45 4e 44 0d 0a 43 = 12.0; ..END..C
09a0: 41 53 45 28 33 29 0d 0a 09 69 6e 74 20 72 65 76 ASE(3)...int rev
09b0: 65 6e 75 65 73 5f 5b 5d 20 3d 20 7b 30 2c 20 30 enues_[] = {0, 0
09c0: 2c 20 30 2c 20 30 2c 20 30 2c 20 31 30 30 7d 3b , 0, 0, 0, 100};
09d0: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 ... vector <int
09e0: 3e 20 72 65 76 65 6e 75 65 73 28 72 65 76 65 6e > revenues(reven
09f0: 75 65 73 5f 2c 20 72 65 76 65 6e 75 65 73 5f 2b ues_, revenues_+
0a00: 73 69 7a 65 6f 66 28 72 65 76 65 6e 75 65 73 5f sizeof(revenues_
0a10: 29 2f 73 69 7a 65 6f 66 28 2a 72 65 76 65 6e 75 )/sizeof(*revenu
0a20: 65 73 5f 29 29 3b 20 0d 0a 09 64 6f 75 62 6c 65 es_)); ...double
0a30: 20 5f 20 3d 20 35 30 2e 30 3b 20 0d 0a 45 4e 44 _ = 50.0; ..END
0a40: 0d 0a 43 41 53 45 28 34 29 0d 0a 09 69 6e 74 20 ..CASE(4)...int
0a50: 72 65 76 65 6e 75 65 73 5f 5b 5d 20 3d 20 7b 31 revenues_[] = {1
0a60: 30 2c 20 2d 31 30 2c 20 31 30 30 2c 20 2d 31 30 0, -10, 100, -10
0a70: 30 2c 20 31 30 30 30 2c 20 2d 31 30 30 30 7d 3b 0, 1000, -1000};
0a80: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 ... vector <int
0a90: 3e 20 72 65 76 65 6e 75 65 73 28 72 65 76 65 6e > revenues(reven
0aa0: 75 65 73 5f 2c 20 72 65 76 65 6e 75 65 73 5f 2b ues_, revenues_+
0ab0: 73 69 7a 65 6f 66 28 72 65 76 65 6e 75 65 73 5f sizeof(revenues_
0ac0: 29 2f 73 69 7a 65 6f 66 28 2a 72 65 76 65 6e 75 )/sizeof(*revenu
0ad0: 65 73 5f 29 29 3b 20 0d 0a 09 64 6f 75 62 6c 65 es_)); ...double
0ae0: 20 5f 20 3d 20 34 39 31 2e 32 35 3b 20 0d 0a 45 _ = 491.25; ..E
0af0: 4e 44 0d 0a 43 41 53 45 28 35 29 0d 0a 69 6e 74 ND..CASE(5)..int
0b00: 20 72 65 76 65 6e 75 65 73 5f 5b 5d 20 3d 20 7b revenues_[] = {
0b10: 30 2c 30 2c 31 30 30 2c 31 30 30 7d 3b 0d 0a 09 0,0,100,100};...
0b20: 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 72 vector <int> r
0b30: 65 76 65 6e 75 65 73 28 72 65 76 65 6e 75 65 73 evenues(revenues
0b40: 5f 2c 20 72 65 76 65 6e 75 65 73 5f 2b 73 69 7a _, revenues_+siz
0b50: 65 6f 66 28 72 65 76 65 6e 75 65 73 5f 29 2f 73 eof(revenues_)/s
0b60: 69 7a 65 6f 66 28 2a 72 65 76 65 6e 75 65 73 5f izeof(*revenues_
0b70: 29 29 3b 20 0d 0a 09 64 6f 75 62 6c 65 20 5f 20 )); ...double _
0b80: 3d 20 2d 31 3b 20 0d 0a 45 4e 44 0d 0a 2f 2a 0d = -1; ..END../*.
0b90: 0a 43 41 53 45 28 36 29 0d 0a 09 69 6e 74 20 72 .CASE(6)...int r
0ba0: 65 76 65 6e 75 65 73 5f 5b 5d 20 3d 20 3b 0d 0a evenues_[] = ;..
0bb0: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
0bc0: 72 65 76 65 6e 75 65 73 28 72 65 76 65 6e 75 65 revenues(revenue
0bd0: 73 5f 2c 20 72 65 76 65 6e 75 65 73 5f 2b 73 69 s_, revenues_+si
0be0: 7a 65 6f 66 28 72 65 76 65 6e 75 65 73 5f 29 2f zeof(revenues_)/
0bf0: 73 69 7a 65 6f 66 28 2a 72 65 76 65 6e 75 65 73 sizeof(*revenues
0c00: 5f 29 29 3b 20 0d 0a 09 64 6f 75 62 6c 65 20 5f _)); ...double _
0c10: 20 3d 20 3b 20 0d 0a 45 4e 44 0d 0a 2a 2f 0d 0a = ; ..END..*/..
0c20: 7d 0d 0a 2f 2f 20 45 4e 44 20 43 55 54 20 48 45 }..// END CUT HE
0c30: 52 45 0d 0a RE..