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 74 75 70 6c 65 3e 0d 0a 75 73 69 6e 67 20 6e <tuple>..using n
0150: 61 6d 65 73 70 61 63 65 20 73 74 64 3b 0d 0a 74 amespace std;..t
0160: 79 70 65 64 65 66 20 6c 6f 6e 67 20 6c 6f 6e 67 ypedef long long
0170: 20 4c 4c 3b 0d 0a 74 79 70 65 64 65 66 20 63 6f LL;..typedef co
0180: 6d 70 6c 65 78 3c 64 6f 75 62 6c 65 3e 20 43 4d mplex<double> CM
0190: 50 3b 0d 0a 0d 0a 63 6c 61 73 73 20 50 72 6f 70 P;....class Prop
01a0: 6f 73 61 6c 4f 70 74 69 6d 69 7a 61 74 69 6f 6e osalOptimization
01b0: 20 7b 20 70 75 62 6c 69 63 3a 0d 0a 09 64 6f 75 { public:...dou
01c0: 62 6c 65 20 62 65 73 74 50 61 74 68 28 69 6e 74 ble bestPath(int
01d0: 20 52 2c 20 69 6e 74 20 43 2c 20 69 6e 74 20 4b R, int C, int K
01e0: 2c 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 72 , vector <int> r
01f0: 6f 73 65 73 2c 20 76 65 63 74 6f 72 20 3c 69 6e oses, vector <in
0200: 74 3e 20 74 75 6c 69 70 73 2c 20 76 65 63 74 6f t> tulips, vecto
0210: 72 20 3c 69 6e 74 3e 20 63 6f 73 74 73 29 0d 0a r <int> costs)..
0220: 09 7b 0d 0a 09 09 69 6e 74 20 53 20 3d 20 28 52 .{....int S = (R
0230: 20 2d 20 31 29 20 2b 20 28 43 20 2d 20 31 29 3b - 1) + (C - 1);
0240: 0d 0a 0d 0a 09 09 76 65 63 74 6f 72 3c 76 65 63 ......vector<vec
0250: 74 6f 72 3c 74 75 70 6c 65 3c 4c 4c 2c 20 4c 4c tor<tuple<LL, LL
0260: 2c 20 4c 4c 3e 3e 3e 20 63 61 6e 64 31 28 52 2a , LL>>> cand1(R*
0270: 43 29 2c 20 63 61 6e 64 32 28 52 2a 43 29 3b 0d C), cand2(R*C);.
0280: 0a 09 09 64 66 73 31 28 52 2c 20 43 2c 20 4b 2c ...dfs1(R, C, K,
0290: 20 72 6f 73 65 73 2c 20 74 75 6c 69 70 73 2c 20 roses, tulips,
02a0: 63 6f 73 74 73 2c 20 30 2c 20 30 2c 20 53 2f 32 costs, 0, 0, S/2
02b0: 2c 20 30 4c 4c 2c 20 30 4c 4c 2c 20 30 4c 4c 2c , 0LL, 0LL, 0LL,
02c0: 20 63 61 6e 64 31 29 3b 0d 0a 09 09 64 66 73 32 cand1);....dfs2
02d0: 28 52 2c 20 43 2c 20 4b 2c 20 72 6f 73 65 73 2c (R, C, K, roses,
02e0: 20 74 75 6c 69 70 73 2c 20 63 6f 73 74 73 2c 20 tulips, costs,
02f0: 52 2d 31 2c 20 43 2d 31 2c 20 53 2d 53 2f 32 2c R-1, C-1, S-S/2,
0300: 20 30 4c 4c 2c 20 30 4c 4c 2c 20 30 4c 4c 2c 20 0LL, 0LL, 0LL,
0310: 63 61 6e 64 32 29 3b 0d 0a 0d 0a 09 09 64 6f 75 cand2);......dou
0320: 62 6c 65 20 62 65 73 74 20 3d 20 2d 31 3b 0d 0a ble best = -1;..
0330: 09 09 66 6f 72 20 28 69 6e 74 20 69 20 3d 20 30 ..for (int i = 0
0340: 3b 20 69 20 3c 20 63 61 6e 64 31 2e 73 69 7a 65 ; i < cand1.size
0350: 28 29 3b 20 2b 2b 69 29 0d 0a 09 09 09 69 66 20 (); ++i).....if
0360: 28 21 63 61 6e 64 31 5b 69 5d 2e 65 6d 70 74 79 (!cand1[i].empty
0370: 28 29 20 26 26 20 21 63 61 6e 64 32 5b 69 5d 2e () && !cand2[i].
0380: 65 6d 70 74 79 28 29 29 0d 0a 09 09 09 09 62 65 empty())......be
0390: 73 74 20 3d 20 6d 61 78 28 62 65 73 74 2c 20 63 st = max(best, c
03a0: 61 6c 63 5f 62 65 73 74 28 63 61 6e 64 31 5b 69 alc_best(cand1[i
03b0: 5d 2c 20 63 61 6e 64 32 5b 69 5d 2c 20 4b 29 29 ], cand2[i], K))
03c0: 3b 0d 0a 09 09 72 65 74 75 72 6e 20 62 65 73 74 ;....return best
03d0: 3b 0d 0a 09 7d 0d 0a 0d 0a 09 64 6f 75 62 6c 65 ;...}.....double
03e0: 20 63 61 6c 63 5f 62 65 73 74 28 0d 0a 09 09 76 calc_best(....v
03f0: 65 63 74 6f 72 3c 74 75 70 6c 65 3c 4c 4c 2c 20 ector<tuple<LL,
0400: 4c 4c 2c 20 4c 4c 3e 3e 20 63 31 2c 0d 0a 09 09 LL, LL>> c1,....
0410: 76 65 63 74 6f 72 3c 74 75 70 6c 65 3c 4c 4c 2c vector<tuple<LL,
0420: 20 4c 4c 2c 20 4c 4c 3e 3e 20 63 32 2c 0d 0a 09 LL, LL>> c2,...
0430: 09 69 6e 74 20 4b 0d 0a 09 29 20 7b 0d 0a 09 09 .int K...) {....
0440: 73 6f 72 74 28 63 31 2e 62 65 67 69 6e 28 29 2c sort(c1.begin(),
0450: 20 63 31 2e 65 6e 64 28 29 2c 20 5b 26 5d 28 63 c1.end(), [&](c
0460: 6f 6e 73 74 20 74 75 70 6c 65 3c 4c 4c 2c 20 4c onst tuple<LL, L
0470: 4c 2c 20 4c 4c 3e 26 20 61 2c 20 63 6f 6e 73 74 L, LL>& a, const
0480: 20 74 75 70 6c 65 3c 4c 4c 2c 20 4c 4c 2c 20 4c tuple<LL, LL, L
0490: 4c 3e 26 20 62 29 20 7b 0d 0a 09 09 09 72 65 74 L>& b) {.....ret
04a0: 75 72 6e 20 64 6f 75 62 6c 65 28 67 65 74 3c 30 urn double(get<0
04b0: 3e 28 61 29 29 20 2f 20 67 65 74 3c 31 3e 28 61 >(a)) / get<1>(a
04c0: 29 20 3e 20 64 6f 75 62 6c 65 28 67 65 74 3c 30 ) > double(get<0
04d0: 3e 28 62 29 29 20 2f 20 67 65 74 3c 31 3e 28 62 >(b)) / get<1>(b
04e0: 29 3b 0d 0a 09 09 7d 29 3b 0d 0a 09 09 73 6f 72 );....});....sor
04f0: 74 28 63 32 2e 62 65 67 69 6e 28 29 2c 20 63 32 t(c2.begin(), c2
0500: 2e 65 6e 64 28 29 2c 20 5b 26 5d 28 63 6f 6e 73 .end(), [&](cons
0510: 74 20 74 75 70 6c 65 3c 4c 4c 2c 20 4c 4c 2c 20 t tuple<LL, LL,
0520: 4c 4c 3e 26 20 61 2c 20 63 6f 6e 73 74 20 74 75 LL>& a, const tu
0530: 70 6c 65 3c 4c 4c 2c 20 4c 4c 2c 20 4c 4c 3e 26 ple<LL, LL, LL>&
0540: 20 62 29 20 7b 0d 0a 09 09 09 72 65 74 75 72 6e b) {.....return
0550: 20 64 6f 75 62 6c 65 28 67 65 74 3c 30 3e 28 61 double(get<0>(a
0560: 29 29 20 2f 20 67 65 74 3c 31 3e 28 61 29 20 3e )) / get<1>(a) >
0570: 20 64 6f 75 62 6c 65 28 67 65 74 3c 30 3e 28 62 double(get<0>(b
0580: 29 29 20 2f 20 67 65 74 3c 31 3e 28 62 29 3b 0d )) / get<1>(b);.
0590: 0a 09 09 7d 29 3b 0d 0a 09 09 64 6f 75 62 6c 65 ...});....double
05a0: 20 62 65 73 74 20 3d 20 2d 31 3b 0d 0a 09 09 66 best = -1;....f
05b0: 6f 72 20 28 61 75 74 6f 26 26 20 65 31 20 3a 20 or (auto&& e1 :
05c0: 63 31 29 20 7b 0d 0a 09 09 09 4c 4c 20 72 31 2c c1) {.....LL r1,
05d0: 20 74 31 2c 20 63 6f 31 3b 20 74 69 65 28 72 31 t1, co1; tie(r1
05e0: 2c 20 74 31 2c 20 63 6f 31 29 20 3d 20 65 31 3b , t1, co1) = e1;
05f0: 0d 0a 09 09 09 64 6f 75 62 6c 65 20 72 61 74 31 .....double rat1
0600: 20 3d 20 64 6f 75 62 6c 65 28 72 31 29 20 2f 20 = double(r1) /
0610: 74 31 3b 0d 0a 09 09 09 66 6f 72 20 28 61 75 74 t1;.....for (aut
0620: 6f 26 26 20 65 32 20 3a 20 63 32 29 20 7b 0d 0a o&& e2 : c2) {..
0630: 09 09 09 09 4c 4c 20 72 32 2c 20 74 32 2c 20 63 ....LL r2, t2, c
0640: 6f 32 3b 20 74 69 65 28 72 32 2c 20 74 32 2c 20 o2; tie(r2, t2,
0650: 63 6f 32 29 20 3d 20 65 32 3b 0d 0a 09 09 09 09 co2) = e2;......
0660: 64 6f 75 62 6c 65 20 72 61 74 32 20 3d 20 64 6f double rat2 = do
0670: 75 62 6c 65 28 72 32 29 20 2f 20 74 32 3b 0d 0a uble(r2) / t2;..
0680: 09 09 09 09 69 66 20 28 63 6f 31 20 2b 20 63 6f ....if (co1 + co
0690: 32 20 3c 3d 20 4b 29 20 7b 0d 0a 09 09 09 09 09 2 <= K) {.......
06a0: 62 65 73 74 20 3d 20 6d 61 78 28 62 65 73 74 2c best = max(best,
06b0: 20 64 6f 75 62 6c 65 28 72 31 20 2b 20 72 32 29 double(r1 + r2)
06c0: 20 2f 20 28 74 31 20 2b 20 74 32 29 29 3b 0d 0a / (t1 + t2));..
06d0: 09 09 09 09 7d 0d 0a 09 09 09 09 69 66 20 28 72 ....}......if (r
06e0: 61 74 31 20 3c 3d 20 62 65 73 74 20 26 26 20 72 at1 <= best && r
06f0: 61 74 32 20 3c 3d 20 62 65 73 74 29 0d 0a 09 09 at2 <= best)....
0700: 09 09 09 62 72 65 61 6b 3b 0d 0a 09 09 09 7d 0d ...break;.....}.
0710: 0a 09 09 7d 0d 0a 09 09 72 65 74 75 72 6e 20 62 ...}....return b
0720: 65 73 74 3b 0d 0a 09 7d 0d 0a 0d 0a 09 76 6f 69 est;...}.....voi
0730: 64 20 64 66 73 31 28 69 6e 74 20 52 2c 20 69 6e d dfs1(int R, in
0740: 74 20 43 2c 20 69 6e 74 20 4b 2c 20 63 6f 6e 73 t C, int K, cons
0750: 74 20 76 65 63 74 6f 72 3c 69 6e 74 3e 20 26 72 t vector<int> &r
0760: 6f 73 65 73 2c 20 63 6f 6e 73 74 20 76 65 63 74 oses, const vect
0770: 6f 72 3c 69 6e 74 3e 26 20 74 75 6c 69 70 73 2c or<int>& tulips,
0780: 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 69 6e const vector<in
0790: 74 3e 26 20 63 6f 73 74 73 2c 0d 0a 09 09 69 6e t>& costs,....in
07a0: 74 20 79 2c 20 69 6e 74 20 78 2c 20 69 6e 74 20 t y, int x, int
07b0: 73 2c 20 4c 4c 20 72 72 2c 20 4c 4c 20 74 74 2c s, LL rr, LL tt,
07c0: 20 4c 4c 20 63 63 2c 20 76 65 63 74 6f 72 3c 76 LL cc, vector<v
07d0: 65 63 74 6f 72 3c 74 75 70 6c 65 3c 4c 4c 2c 20 ector<tuple<LL,
07e0: 4c 4c 2c 20 4c 4c 3e 3e 3e 26 20 63 61 6e 64 29 LL, LL>>>& cand)
07f0: 20 7b 0d 0a 09 09 69 66 20 28 73 20 3d 3d 20 30 {....if (s == 0
0800: 29 20 7b 0d 0a 09 09 09 63 61 6e 64 5b 79 2a 43 ) {.....cand[y*C
0810: 2b 78 5d 2e 65 6d 70 6c 61 63 65 5f 62 61 63 6b +x].emplace_back
0820: 28 72 72 2c 20 74 74 2c 20 63 63 29 3b 0d 0a 09 (rr, tt, cc);...
0830: 09 09 72 65 74 75 72 6e 3b 0d 0a 09 09 7d 0d 0a ..return;....}..
0840: 09 09 73 2d 2d 3b 0d 0a 09 09 72 72 20 2b 3d 20 ..s--;....rr +=
0850: 72 6f 73 65 73 5b 79 2a 43 20 2b 20 78 5d 3b 0d roses[y*C + x];.
0860: 0a 09 09 74 74 20 2b 3d 20 74 75 6c 69 70 73 5b ...tt += tulips[
0870: 79 2a 43 20 2b 20 78 5d 3b 0d 0a 09 09 63 63 20 y*C + x];....cc
0880: 2b 3d 20 63 6f 73 74 73 5b 79 2a 43 20 2b 20 78 += costs[y*C + x
0890: 5d 3b 0d 0a 09 09 69 66 20 28 79 20 2b 20 31 20 ];....if (y + 1
08a0: 3c 20 52 29 0d 0a 09 09 09 64 66 73 31 28 52 2c < R).....dfs1(R,
08b0: 20 43 2c 20 4b 2c 20 72 6f 73 65 73 2c 20 74 75 C, K, roses, tu
08c0: 6c 69 70 73 2c 20 63 6f 73 74 73 2c 20 79 2b 31 lips, costs, y+1
08d0: 2c 20 78 2c 20 73 2c 20 72 72 2c 20 74 74 2c 20 , x, s, rr, tt,
08e0: 63 63 2c 20 63 61 6e 64 29 3b 0d 0a 09 09 69 66 cc, cand);....if
08f0: 20 28 78 20 2b 20 31 20 3c 20 43 29 0d 0a 09 09 (x + 1 < C)....
0900: 09 64 66 73 31 28 52 2c 20 43 2c 20 4b 2c 20 72 .dfs1(R, C, K, r
0910: 6f 73 65 73 2c 20 74 75 6c 69 70 73 2c 20 63 6f oses, tulips, co
0920: 73 74 73 2c 20 79 2c 20 78 2b 31 2c 20 73 2c 20 sts, y, x+1, s,
0930: 72 72 2c 20 74 74 2c 20 63 63 2c 20 63 61 6e 64 rr, tt, cc, cand
0940: 29 3b 0d 0a 09 7d 0d 0a 09 76 6f 69 64 20 64 66 );...}...void df
0950: 73 32 28 69 6e 74 20 52 2c 20 69 6e 74 20 43 2c s2(int R, int C,
0960: 20 69 6e 74 20 4b 2c 20 63 6f 6e 73 74 20 76 65 int K, const ve
0970: 63 74 6f 72 3c 69 6e 74 3e 20 26 72 6f 73 65 73 ctor<int> &roses
0980: 2c 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 69 , const vector<i
0990: 6e 74 3e 26 20 74 75 6c 69 70 73 2c 20 63 6f 6e nt>& tulips, con
09a0: 73 74 20 76 65 63 74 6f 72 3c 69 6e 74 3e 26 20 st vector<int>&
09b0: 63 6f 73 74 73 2c 0d 0a 09 09 69 6e 74 20 79 2c costs,....int y,
09c0: 20 69 6e 74 20 78 2c 20 69 6e 74 20 73 2c 20 4c int x, int s, L
09d0: 4c 20 72 72 2c 20 4c 4c 20 74 74 2c 20 4c 4c 20 L rr, LL tt, LL
09e0: 63 63 2c 20 76 65 63 74 6f 72 3c 76 65 63 74 6f cc, vector<vecto
09f0: 72 3c 74 75 70 6c 65 3c 4c 4c 2c 20 4c 4c 2c 20 r<tuple<LL, LL,
0a00: 4c 4c 3e 3e 3e 26 20 63 61 6e 64 29 20 7b 0d 0a LL>>>& cand) {..
0a10: 09 09 72 72 20 2b 3d 20 72 6f 73 65 73 5b 79 2a ..rr += roses[y*
0a20: 43 20 2b 20 78 5d 3b 0d 0a 09 09 74 74 20 2b 3d C + x];....tt +=
0a30: 20 74 75 6c 69 70 73 5b 79 2a 43 20 2b 20 78 5d tulips[y*C + x]
0a40: 3b 0d 0a 09 09 63 63 20 2b 3d 20 63 6f 73 74 73 ;....cc += costs
0a50: 5b 79 2a 43 20 2b 20 78 5d 3b 0d 0a 09 09 69 66 [y*C + x];....if
0a60: 20 28 73 20 3d 3d 20 30 29 20 7b 0d 0a 09 09 09 (s == 0) {.....
0a70: 63 61 6e 64 5b 79 2a 43 2b 78 5d 2e 65 6d 70 6c cand[y*C+x].empl
0a80: 61 63 65 5f 62 61 63 6b 28 72 72 2c 20 74 74 2c ace_back(rr, tt,
0a90: 20 63 63 29 3b 0d 0a 09 09 09 72 65 74 75 72 6e cc);.....return
0aa0: 3b 0d 0a 09 09 7d 0d 0a 09 09 73 2d 2d 3b 0d 0a ;....}....s--;..
0ab0: 09 09 69 66 20 28 79 20 2d 20 31 20 3e 3d 20 30 ..if (y - 1 >= 0
0ac0: 29 0d 0a 09 09 09 64 66 73 32 28 52 2c 20 43 2c ).....dfs2(R, C,
0ad0: 20 4b 2c 20 72 6f 73 65 73 2c 20 74 75 6c 69 70 K, roses, tulip
0ae0: 73 2c 20 63 6f 73 74 73 2c 20 79 20 2d 20 31 2c s, costs, y - 1,
0af0: 20 78 2c 20 73 2c 20 72 72 2c 20 74 74 2c 20 63 x, s, rr, tt, c
0b00: 63 2c 20 63 61 6e 64 29 3b 0d 0a 09 09 69 66 20 c, cand);....if
0b10: 28 78 20 2d 20 31 20 3e 3d 20 30 29 0d 0a 09 09 (x - 1 >= 0)....
0b20: 09 64 66 73 32 28 52 2c 20 43 2c 20 4b 2c 20 72 .dfs2(R, C, K, r
0b30: 6f 73 65 73 2c 20 74 75 6c 69 70 73 2c 20 63 6f oses, tulips, co
0b40: 73 74 73 2c 20 79 2c 20 78 20 2d 20 31 2c 20 73 sts, y, x - 1, s
0b50: 2c 20 72 72 2c 20 74 74 2c 20 63 63 2c 20 63 61 , rr, tt, cc, ca
0b60: 6e 64 29 3b 0d 0a 09 7d 0d 0a 7d 3b 0d 0a 0d 0a nd);...}..};....
0b70: 2f 2f 20 42 45 47 49 4e 20 43 55 54 20 48 45 52 // BEGIN CUT HER
0b80: 45 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 74 69 E..#include <cti
0b90: 6d 65 3e 0d 0a 64 6f 75 62 6c 65 20 73 74 61 72 me>..double star
0ba0: 74 5f 74 69 6d 65 3b 20 73 74 72 69 6e 67 20 74 t_time; string t
0bb0: 69 6d 65 72 28 29 0d 0a 20 7b 20 6f 73 74 72 69 imer().. { ostri
0bc0: 6e 67 73 74 72 65 61 6d 20 6f 73 3b 20 6f 73 20 ngstream os; os
0bd0: 3c 3c 20 22 20 28 22 20 3c 3c 20 69 6e 74 28 28 << " (" << int((
0be0: 63 6c 6f 63 6b 28 29 2d 73 74 61 72 74 5f 74 69 clock()-start_ti
0bf0: 6d 65 29 2f 43 4c 4f 43 4b 53 5f 50 45 52 5f 53 me)/CLOCKS_PER_S
0c00: 45 43 2a 31 30 30 30 29 20 3c 3c 20 22 20 6d 73 EC*1000) << " ms
0c10: 65 63 29 22 3b 20 72 65 74 75 72 6e 20 6f 73 2e ec)"; return os.
0c20: 73 74 72 28 29 3b 20 7d 0d 0a 74 65 6d 70 6c 61 str(); }..templa
0c30: 74 65 3c 74 79 70 65 6e 61 6d 65 20 54 3e 20 6f te<typename T> o
0c40: 73 74 72 65 61 6d 26 20 6f 70 65 72 61 74 6f 72 stream& operator
0c50: 3c 3c 28 6f 73 74 72 65 61 6d 26 20 6f 73 2c 20 <<(ostream& os,
0c60: 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 54 3e 26 const vector<T>&
0c70: 20 76 29 0d 0a 20 7b 20 6f 73 20 3c 3c 20 22 7b v).. { os << "{
0c80: 20 22 3b 0d 0a 20 20 20 66 6f 72 28 74 79 70 65 ";.. for(type
0c90: 6e 61 6d 65 20 76 65 63 74 6f 72 3c 54 3e 3a 3a name vector<T>::
0ca0: 63 6f 6e 73 74 5f 69 74 65 72 61 74 6f 72 20 69 const_iterator i
0cb0: 74 3d 76 2e 62 65 67 69 6e 28 29 3b 20 69 74 21 t=v.begin(); it!
0cc0: 3d 76 2e 65 6e 64 28 29 3b 20 2b 2b 69 74 29 0d =v.end(); ++it).
0cd0: 0a 20 20 20 6f 73 20 3c 3c 20 27 5c 22 27 20 3c . os << '\"' <
0ce0: 3c 20 2a 69 74 20 3c 3c 20 27 5c 22 27 20 3c 3c < *it << '\"' <<
0cf0: 20 28 69 74 2b 31 3d 3d 76 2e 65 6e 64 28 29 20 (it+1==v.end()
0d00: 3f 20 22 22 20 3a 20 22 2c 20 22 29 3b 20 6f 73 ? "" : ", "); os
0d10: 20 3c 3c 20 22 20 7d 22 3b 20 72 65 74 75 72 6e << " }"; return
0d20: 20 6f 73 3b 20 7d 0d 0a 76 6f 69 64 20 76 65 72 os; }..void ver
0d30: 69 66 79 5f 63 61 73 65 28 63 6f 6e 73 74 20 64 ify_case(const d
0d40: 6f 75 62 6c 65 26 20 45 78 70 65 63 74 65 64 2c ouble& Expected,
0d50: 20 63 6f 6e 73 74 20 64 6f 75 62 6c 65 26 20 52 const double& R
0d60: 65 63 65 69 76 65 64 29 20 7b 0d 0a 20 62 6f 6f eceived) {.. boo
0d70: 6c 20 6f 6b 20 3d 20 28 61 62 73 28 45 78 70 65 l ok = (abs(Expe
0d80: 63 74 65 64 20 2d 20 52 65 63 65 69 76 65 64 29 cted - Received)
0d90: 20 3c 20 31 65 2d 39 29 3b 0d 0a 20 69 66 28 6f < 1e-9);.. if(o
0da0: 6b 29 20 63 65 72 72 20 3c 3c 20 22 50 41 53 53 k) cerr << "PASS
0db0: 45 44 22 20 3c 3c 20 74 69 6d 65 72 28 29 20 3c ED" << timer() <
0dc0: 3c 20 65 6e 64 6c 3b 20 20 65 6c 73 65 20 7b 20 < endl; else {
0dd0: 63 65 72 72 20 3c 3c 20 22 46 41 49 4c 45 44 22 cerr << "FAILED"
0de0: 20 3c 3c 20 74 69 6d 65 72 28 29 20 3c 3c 20 65 << timer() << e
0df0: 6e 64 6c 3b 0d 0a 20 63 65 72 72 20 3c 3c 20 22 ndl;.. cerr << "
0e00: 5c 74 6f 3a 20 5c 22 22 20 3c 3c 20 45 78 70 65 \to: \"" << Expe
0e10: 63 74 65 64 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 cted << '\"' <<
0e20: 65 6e 64 6c 20 3c 3c 20 22 5c 74 78 3a 20 5c 22 endl << "\tx: \"
0e30: 22 20 3c 3c 20 52 65 63 65 69 76 65 64 20 3c 3c " << Received <<
0e40: 20 27 5c 22 27 20 3c 3c 20 65 6e 64 6c 3b 20 7d '\"' << endl; }
0e50: 20 7d 0d 0a 23 64 65 66 69 6e 65 20 43 41 53 45 }..#define CASE
0e60: 28 4e 29 20 7b 63 65 72 72 20 3c 3c 20 22 54 65 (N) {cerr << "Te
0e70: 73 74 20 43 61 73 65 20 23 22 20 3c 3c 20 4e 20 st Case #" << N
0e80: 3c 3c 20 22 2e 2e 2e 22 20 3c 3c 20 66 6c 75 73 << "..." << flus
0e90: 68 3b 20 73 74 61 72 74 5f 74 69 6d 65 3d 63 6c h; start_time=cl
0ea0: 6f 63 6b 28 29 3b 0d 0a 23 64 65 66 69 6e 65 20 ock();..#define
0eb0: 45 4e 44 09 20 76 65 72 69 66 79 5f 63 61 73 65 END. verify_case
0ec0: 28 5f 2c 20 50 72 6f 70 6f 73 61 6c 4f 70 74 69 (_, ProposalOpti
0ed0: 6d 69 7a 61 74 69 6f 6e 28 29 2e 62 65 73 74 50 mization().bestP
0ee0: 61 74 68 28 52 2c 20 43 2c 20 4b 2c 20 72 6f 73 ath(R, C, K, ros
0ef0: 65 73 2c 20 74 75 6c 69 70 73 2c 20 63 6f 73 74 es, tulips, cost
0f00: 73 29 29 3b 7d 0d 0a 69 6e 74 20 6d 61 69 6e 28 s));}..int main(
0f10: 29 7b 0d 0a 0d 0a 43 41 53 45 28 30 29 0d 0a 09 ){....CASE(0)...
0f20: 69 6e 74 20 52 20 3d 20 32 3b 20 0d 0a 09 69 6e int R = 2; ...in
0f30: 74 20 43 20 3d 20 32 3b 20 0d 0a 09 69 6e 74 20 t C = 2; ...int
0f40: 4b 20 3d 20 31 30 30 3b 20 0d 0a 09 69 6e 74 20 K = 100; ...int
0f50: 72 6f 73 65 73 5f 5b 5d 20 3d 20 7b 30 2c 20 32 roses_[] = {0, 2
0f60: 2c 20 33 2c 20 30 7d 3b 0d 0a 09 20 20 76 65 63 , 3, 0};... vec
0f70: 74 6f 72 20 3c 69 6e 74 3e 20 72 6f 73 65 73 28 tor <int> roses(
0f80: 72 6f 73 65 73 5f 2c 20 72 6f 73 65 73 5f 2b 73 roses_, roses_+s
0f90: 69 7a 65 6f 66 28 72 6f 73 65 73 5f 29 2f 73 69 izeof(roses_)/si
0fa0: 7a 65 6f 66 28 2a 72 6f 73 65 73 5f 29 29 3b 20 zeof(*roses_));
0fb0: 0d 0a 09 69 6e 74 20 74 75 6c 69 70 73 5f 5b 5d ...int tulips_[]
0fc0: 20 3d 20 7b 30 2c 20 33 2c 20 35 2c 20 30 7d 3b = {0, 3, 5, 0};
0fd0: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 ... vector <int
0fe0: 3e 20 74 75 6c 69 70 73 28 74 75 6c 69 70 73 5f > tulips(tulips_
0ff0: 2c 20 74 75 6c 69 70 73 5f 2b 73 69 7a 65 6f 66 , tulips_+sizeof
1000: 28 74 75 6c 69 70 73 5f 29 2f 73 69 7a 65 6f 66 (tulips_)/sizeof
1010: 28 2a 74 75 6c 69 70 73 5f 29 29 3b 20 0d 0a 09 (*tulips_)); ...
1020: 69 6e 74 20 63 6f 73 74 73 5f 5b 5d 20 3d 20 7b int costs_[] = {
1030: 30 2c 20 37 30 2c 20 38 30 2c 20 30 7d 3b 0d 0a 0, 70, 80, 0};..
1040: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
1050: 63 6f 73 74 73 28 63 6f 73 74 73 5f 2c 20 63 6f costs(costs_, co
1060: 73 74 73 5f 2b 73 69 7a 65 6f 66 28 63 6f 73 74 sts_+sizeof(cost
1070: 73 5f 29 2f 73 69 7a 65 6f 66 28 2a 63 6f 73 74 s_)/sizeof(*cost
1080: 73 5f 29 29 3b 20 0d 0a 09 64 6f 75 62 6c 65 20 s_)); ...double
1090: 5f 20 3d 20 30 2e 36 36 36 36 36 36 36 36 36 36 _ = 0.6666666666
10a0: 36 36 36 36 36 37 3b 20 0d 0a 45 4e 44 0d 0a 43 666667; ..END..C
10b0: 41 53 45 28 31 29 0d 0a 09 69 6e 74 20 52 20 3d ASE(1)...int R =
10c0: 20 32 3b 20 0d 0a 09 69 6e 74 20 43 20 3d 20 32 2; ...int C = 2
10d0: 3b 20 0d 0a 09 69 6e 74 20 4b 20 3d 20 31 30 30 ; ...int K = 100
10e0: 3b 20 0d 0a 09 69 6e 74 20 72 6f 73 65 73 5f 5b ; ...int roses_[
10f0: 5d 20 3d 20 7b 30 2c 20 32 2c 20 33 2c 20 30 7d ] = {0, 2, 3, 0}
1100: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e ;... vector <in
1110: 74 3e 20 72 6f 73 65 73 28 72 6f 73 65 73 5f 2c t> roses(roses_,
1120: 20 72 6f 73 65 73 5f 2b 73 69 7a 65 6f 66 28 72 roses_+sizeof(r
1130: 6f 73 65 73 5f 29 2f 73 69 7a 65 6f 66 28 2a 72 oses_)/sizeof(*r
1140: 6f 73 65 73 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 oses_)); ...int
1150: 74 75 6c 69 70 73 5f 5b 5d 20 3d 20 7b 30 2c 20 tulips_[] = {0,
1160: 33 2c 20 35 2c 20 30 7d 3b 0d 0a 09 20 20 76 65 3, 5, 0};... ve
1170: 63 74 6f 72 20 3c 69 6e 74 3e 20 74 75 6c 69 70 ctor <int> tulip
1180: 73 28 74 75 6c 69 70 73 5f 2c 20 74 75 6c 69 70 s(tulips_, tulip
1190: 73 5f 2b 73 69 7a 65 6f 66 28 74 75 6c 69 70 73 s_+sizeof(tulips
11a0: 5f 29 2f 73 69 7a 65 6f 66 28 2a 74 75 6c 69 70 _)/sizeof(*tulip
11b0: 73 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 63 6f 73 s_)); ...int cos
11c0: 74 73 5f 5b 5d 20 3d 20 7b 30 2c 20 31 37 30 2c ts_[] = {0, 170,
11d0: 20 31 30 30 2c 20 30 7d 3b 0d 0a 09 20 20 76 65 100, 0};... ve
11e0: 63 74 6f 72 20 3c 69 6e 74 3e 20 63 6f 73 74 73 ctor <int> costs
11f0: 28 63 6f 73 74 73 5f 2c 20 63 6f 73 74 73 5f 2b (costs_, costs_+
1200: 73 69 7a 65 6f 66 28 63 6f 73 74 73 5f 29 2f 73 sizeof(costs_)/s
1210: 69 7a 65 6f 66 28 2a 63 6f 73 74 73 5f 29 29 3b izeof(*costs_));
1220: 20 0d 0a 09 64 6f 75 62 6c 65 20 5f 20 3d 20 30 ...double _ = 0
1230: 2e 36 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 .6; ..END..CASE(
1240: 32 29 0d 0a 09 69 6e 74 20 52 20 3d 20 33 3b 20 2)...int R = 3;
1250: 0d 0a 09 69 6e 74 20 43 20 3d 20 33 3b 20 0d 0a ...int C = 3; ..
1260: 09 69 6e 74 20 4b 20 3d 20 39 38 3b 20 0d 0a 09 .int K = 98; ...
1270: 69 6e 74 20 72 6f 73 65 73 5f 5b 5d 20 3d 20 7b int roses_[] = {
1280: 30 2c 20 31 2c 20 31 2c 20 31 2c 20 31 2c 20 31 0, 1, 1, 1, 1, 1
1290: 2c 20 31 2c 20 31 2c 20 30 7d 3b 0d 0a 09 20 20 , 1, 1, 0};...
12a0: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 72 6f 73 vector <int> ros
12b0: 65 73 28 72 6f 73 65 73 5f 2c 20 72 6f 73 65 73 es(roses_, roses
12c0: 5f 2b 73 69 7a 65 6f 66 28 72 6f 73 65 73 5f 29 _+sizeof(roses_)
12d0: 2f 73 69 7a 65 6f 66 28 2a 72 6f 73 65 73 5f 29 /sizeof(*roses_)
12e0: 29 3b 20 0d 0a 09 69 6e 74 20 74 75 6c 69 70 73 ); ...int tulips
12f0: 5f 5b 5d 20 3d 20 7b 30 2c 20 31 2c 20 31 2c 20 _[] = {0, 1, 1,
1300: 31 2c 20 31 2c 20 31 2c 20 31 2c 20 31 2c 20 30 1, 1, 1, 1, 1, 0
1310: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 };... vector <i
1320: 6e 74 3e 20 74 75 6c 69 70 73 28 74 75 6c 69 70 nt> tulips(tulip
1330: 73 5f 2c 20 74 75 6c 69 70 73 5f 2b 73 69 7a 65 s_, tulips_+size
1340: 6f 66 28 74 75 6c 69 70 73 5f 29 2f 73 69 7a 65 of(tulips_)/size
1350: 6f 66 28 2a 74 75 6c 69 70 73 5f 29 29 3b 20 0d of(*tulips_)); .
1360: 0a 09 69 6e 74 20 63 6f 73 74 73 5f 5b 5d 20 3d ..int costs_[] =
1370: 20 7b 30 2c 20 33 33 2c 20 33 33 2c 20 33 33 2c {0, 33, 33, 33,
1380: 20 33 33 2c 20 33 33 2c 20 33 33 2c 20 33 33 2c 33, 33, 33, 33,
1390: 20 30 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 0};... vector
13a0: 3c 69 6e 74 3e 20 63 6f 73 74 73 28 63 6f 73 74 <int> costs(cost
13b0: 73 5f 2c 20 63 6f 73 74 73 5f 2b 73 69 7a 65 6f s_, costs_+sizeo
13c0: 66 28 63 6f 73 74 73 5f 29 2f 73 69 7a 65 6f 66 f(costs_)/sizeof
13d0: 28 2a 63 6f 73 74 73 5f 29 29 3b 20 0d 0a 09 64 (*costs_)); ...d
13e0: 6f 75 62 6c 65 20 5f 20 3d 20 2d 31 2e 30 3b 20 ouble _ = -1.0;
13f0: 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 33 29 0d 0a ..END..CASE(3)..
1400: 09 69 6e 74 20 52 20 3d 20 35 3b 20 0d 0a 09 69 .int R = 5; ...i
1410: 6e 74 20 43 20 3d 20 39 3b 20 0d 0a 09 69 6e 74 nt C = 9; ...int
1420: 20 4b 20 3d 20 36 32 32 3b 20 0d 0a 09 69 6e 74 K = 622; ...int
1430: 20 72 6f 73 65 73 5f 5b 5d 20 3d 20 7b 30 2c 20 roses_[] = {0,
1440: 32 2c 20 31 32 2c 20 31 2c 20 36 2c 20 31 30 2c 2, 12, 1, 6, 10,
1450: 20 31 30 2c 20 32 34 2c 20 33 2c 20 31 2c 20 37 10, 24, 3, 1, 7
1460: 2c 20 34 2c 20 34 2c 20 31 2c 20 33 37 2c 20 34 , 4, 4, 1, 37, 4
1470: 2c 20 36 2c 20 38 2c 20 32 2c 20 32 30 2c 20 35 , 6, 8, 2, 20, 5
1480: 2c 20 32 30 2c 20 36 2c 20 37 2c 20 32 32 2c 20 , 20, 6, 7, 22,
1490: 33 2c 20 32 2c 20 38 2c 20 33 31 2c 20 31 38 2c 3, 2, 8, 31, 18,
14a0: 20 35 2c 20 32 38 2c 20 31 31 2c 20 31 2c 20 33 5, 28, 11, 1, 3
14b0: 34 2c 20 31 2c 20 34 2c 20 32 2c 20 36 2c 20 31 4, 1, 4, 2, 6, 1
14c0: 2c 20 36 2c 20 39 2c 20 35 2c 20 37 2c 20 30 7d , 6, 9, 5, 7, 0}
14d0: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e ;... vector <in
14e0: 74 3e 20 72 6f 73 65 73 28 72 6f 73 65 73 5f 2c t> roses(roses_,
14f0: 20 72 6f 73 65 73 5f 2b 73 69 7a 65 6f 66 28 72 roses_+sizeof(r
1500: 6f 73 65 73 5f 29 2f 73 69 7a 65 6f 66 28 2a 72 oses_)/sizeof(*r
1510: 6f 73 65 73 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 oses_)); ...int
1520: 74 75 6c 69 70 73 5f 5b 5d 20 3d 20 7b 30 2c 20 tulips_[] = {0,
1530: 34 2c 20 33 37 2c 20 32 32 2c 20 33 2c 20 31 34 4, 37, 22, 3, 14
1540: 2c 20 31 30 2c 20 36 2c 20 35 2c 20 36 2c 20 35 , 10, 6, 5, 6, 5
1550: 2c 20 31 37 2c 20 34 2c 20 37 2c 20 31 32 2c 20 , 17, 4, 7, 12,
1560: 33 2c 20 31 2c 20 33 2c 20 33 2c 20 31 2c 20 35 3, 1, 3, 3, 1, 5
1570: 2c 20 31 2c 20 31 31 2c 20 33 37 2c 20 36 2c 20 , 1, 11, 37, 6,
1580: 32 34 2c 20 36 2c 20 33 2c 20 32 31 2c 20 31 2c 24, 6, 3, 21, 1,
1590: 20 32 2c 20 32 37 2c 20 37 2c 20 31 2c 20 38 2c 2, 27, 7, 1, 8,
15a0: 20 31 2c 20 38 2c 20 31 2c 20 32 36 2c 20 32 30 1, 8, 1, 26, 20
15b0: 2c 20 36 2c 20 36 2c 20 36 2c 20 37 2c 20 30 7d , 6, 6, 6, 7, 0}
15c0: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e ;... vector <in
15d0: 74 3e 20 74 75 6c 69 70 73 28 74 75 6c 69 70 73 t> tulips(tulips
15e0: 5f 2c 20 74 75 6c 69 70 73 5f 2b 73 69 7a 65 6f _, tulips_+sizeo
15f0: 66 28 74 75 6c 69 70 73 5f 29 2f 73 69 7a 65 6f f(tulips_)/sizeo
1600: 66 28 2a 74 75 6c 69 70 73 5f 29 29 3b 20 0d 0a f(*tulips_)); ..
1610: 09 69 6e 74 20 63 6f 73 74 73 5f 5b 5d 20 3d 20 .int costs_[] =
1620: 7b 30 2c 20 31 39 2c 20 37 30 2c 20 37 39 2c 20 {0, 19, 70, 79,
1630: 31 38 2c 20 34 33 2c 20 34 39 2c 20 36 35 2c 20 18, 43, 49, 65,
1640: 31 36 2c 20 33 38 2c 20 36 31 2c 20 36 39 2c 20 16, 38, 61, 69,
1650: 34 33 2c 20 31 32 2c 20 36 32 2c 20 31 31 2c 20 43, 12, 62, 11,
1660: 34 34 2c 20 33 35 2c 20 37 2c 20 36 32 2c 20 34 44, 35, 7, 62, 4
1670: 30 2c 20 38 38 2c 20 36 30 2c 20 35 37 2c 20 36 0, 88, 60, 57, 6
1680: 35 2c 20 33 38 2c 20 34 36 2c 20 31 38 2c 20 36 5, 38, 46, 18, 6
1690: 39 2c 20 38 37 2c 20 32 38 2c 20 38 30 2c 20 34 9, 87, 28, 80, 4
16a0: 37 2c 20 35 2c 20 36 34 2c 20 31 2c 20 31 35 2c 7, 5, 64, 1, 15,
16b0: 20 33 2c 20 38 36 2c 20 34 31 2c 20 38 36 2c 20 3, 86, 41, 86,
16c0: 32 31 2c 20 35 36 2c 20 32 38 2c 20 30 7d 3b 0d 21, 56, 28, 0};.
16d0: 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e .. vector <int>
16e0: 20 63 6f 73 74 73 28 63 6f 73 74 73 5f 2c 20 63 costs(costs_, c
16f0: 6f 73 74 73 5f 2b 73 69 7a 65 6f 66 28 63 6f 73 osts_+sizeof(cos
1700: 74 73 5f 29 2f 73 69 7a 65 6f 66 28 2a 63 6f 73 ts_)/sizeof(*cos
1710: 74 73 5f 29 29 3b 20 0d 0a 09 64 6f 75 62 6c 65 ts_)); ...double
1720: 20 5f 20 3d 20 32 2e 31 36 31 32 39 30 33 32 32 _ = 2.161290322
1730: 35 38 30 36 34 35 3b 20 0d 0a 45 4e 44 0d 0a 43 580645; ..END..C
1740: 41 53 45 28 34 29 0d 0a 09 69 6e 74 20 52 20 3d ASE(4)...int R =
1750: 20 32 3b 20 0d 0a 09 69 6e 74 20 43 20 3d 20 33 2; ...int C = 3
1760: 3b 20 0d 0a 09 69 6e 74 20 4b 20 3d 20 31 35 3b ; ...int K = 15;
1770: 20 0d 0a 09 69 6e 74 20 72 6f 73 65 73 5f 5b 5d ...int roses_[]
1780: 20 3d 20 7b 30 2c 20 31 2c 20 33 2c 20 31 2c 20 = {0, 1, 3, 1,
1790: 31 2c 20 30 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 1, 0};... vecto
17a0: 72 20 3c 69 6e 74 3e 20 72 6f 73 65 73 28 72 6f r <int> roses(ro
17b0: 73 65 73 5f 2c 20 72 6f 73 65 73 5f 2b 73 69 7a ses_, roses_+siz
17c0: 65 6f 66 28 72 6f 73 65 73 5f 29 2f 73 69 7a 65 eof(roses_)/size
17d0: 6f 66 28 2a 72 6f 73 65 73 5f 29 29 3b 20 0d 0a of(*roses_)); ..
17e0: 09 69 6e 74 20 74 75 6c 69 70 73 5f 5b 5d 20 3d .int tulips_[] =
17f0: 20 7b 30 2c 20 31 2c 20 32 2c 20 36 2c 20 31 2c {0, 1, 2, 6, 1,
1800: 20 30 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 0};... vector
1810: 3c 69 6e 74 3e 20 74 75 6c 69 70 73 28 74 75 6c <int> tulips(tul
1820: 69 70 73 5f 2c 20 74 75 6c 69 70 73 5f 2b 73 69 ips_, tulips_+si
1830: 7a 65 6f 66 28 74 75 6c 69 70 73 5f 29 2f 73 69 zeof(tulips_)/si
1840: 7a 65 6f 66 28 2a 74 75 6c 69 70 73 5f 29 29 3b zeof(*tulips_));
1850: 20 0d 0a 09 69 6e 74 20 63 6f 73 74 73 5f 5b 5d ...int costs_[]
1860: 20 3d 20 7b 30 2c 20 31 2c 20 31 38 2c 20 39 2c = {0, 1, 18, 9,
1870: 20 31 2c 20 30 7d 3b 0d 0a 09 20 20 76 65 63 74 1, 0};... vect
1880: 6f 72 20 3c 69 6e 74 3e 20 63 6f 73 74 73 28 63 or <int> costs(c
1890: 6f 73 74 73 5f 2c 20 63 6f 73 74 73 5f 2b 73 69 osts_, costs_+si
18a0: 7a 65 6f 66 28 63 6f 73 74 73 5f 29 2f 73 69 7a zeof(costs_)/siz
18b0: 65 6f 66 28 2a 63 6f 73 74 73 5f 29 29 3b 20 0d eof(*costs_)); .
18c0: 0a 09 64 6f 75 62 6c 65 20 5f 20 3d 20 31 2e 30 ..double _ = 1.0
18d0: 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 35 29 ; ..END..CASE(5)
18e0: 0d 0a 09 69 6e 74 20 52 20 3d 20 31 37 3b 20 0d ...int R = 17; .
18f0: 0a 09 69 6e 74 20 43 20 3d 20 31 37 3b 20 0d 0a ..int C = 17; ..
1900: 09 69 6e 74 20 4b 20 3d 20 31 30 30 30 30 30 30 .int K = 1000000
1910: 30 30 30 3b 20 0d 0a 09 69 6e 74 20 72 6f 73 65 000; ...int rose
1920: 73 5f 5b 5d 20 3d 20 7b 20 30 2c 31 37 37 31 33 s_[] = { 0,17713
1930: 2c 39 38 30 30 35 2c 38 35 39 37 32 2c 38 35 34 ,98005,85972,854
1940: 31 39 2c 34 31 33 34 33 2c 34 30 35 39 34 2c 37 19,41343,40594,7
1950: 35 33 34 37 2c 39 33 38 39 30 2c 31 34 34 36 30 5347,93890,14460
1960: 2c 38 38 31 39 32 2c 31 33 32 35 39 2c 35 37 35 ,88192,13259,575
1970: 30 39 2c 32 33 38 36 34 2c 31 31 36 36 35 2c 38 09,23864,11665,8
1980: 33 38 39 31 2c 38 36 32 37 32 2c 31 35 31 37 37 3891,86272,15177
1990: 2c 36 37 34 31 2c 37 31 39 2c 34 35 39 35 34 2c ,6741,719,45954,
19a0: 32 38 39 37 36 2c 31 37 34 39 34 2c 36 39 36 34 28976,17494,6964
19b0: 35 2c 38 35 36 33 35 2c 34 31 36 34 31 2c 38 33 5,85635,41641,83
19c0: 37 35 30 2c 37 32 31 33 34 2c 32 35 34 36 30 2c 750,72134,25460,
19d0: 35 39 32 33 38 2c 37 39 38 34 33 2c 31 39 32 34 59238,79843,1924
19e0: 31 2c 34 32 39 31 30 2c 38 32 30 33 37 2c 37 36 1,42910,82037,76
19f0: 30 31 34 2c 39 34 34 32 34 2c 38 37 38 33 35 2c 014,94424,87835,
1a00: 36 30 35 31 38 2c 38 31 33 38 39 2c 37 31 36 32 60518,81389,7162
1a10: 30 2c 32 32 39 32 35 2c 39 39 38 30 36 2c 39 36 0,22925,99806,96
1a20: 33 38 30 2c 31 33 38 31 32 2c 35 33 39 38 36 2c 380,13812,53986,
1a30: 36 34 30 38 37 2c 37 32 36 34 35 2c 37 31 30 36 64087,72645,7106
1a40: 36 2c 35 39 31 36 37 2c 38 31 35 31 32 2c 37 39 6,59167,81512,79
1a50: 31 31 32 2c 37 39 33 37 36 2c 39 34 31 32 32 2c 112,79376,94122,
1a60: 36 38 39 31 37 2c 36 34 36 31 2c 32 30 38 32 39 68917,6461,20829
1a70: 2c 35 38 32 36 35 2c 32 30 31 39 31 2c 34 39 34 ,58265,20191,494
1a80: 30 33 2c 37 32 31 36 31 2c 37 35 34 36 34 2c 36 03,72161,75464,6
1a90: 33 32 35 35 2c 36 38 34 37 37 2c 39 34 36 31 39 3255,68477,94619
1aa0: 2c 36 30 37 33 31 2c 39 30 30 34 33 2c 32 35 30 ,60731,90043,250
1ab0: 39 39 2c 39 33 34 38 2c 37 38 35 39 34 2c 32 33 99,9348,78594,23
1ac0: 35 31 30 2c 34 32 30 33 35 2c 32 31 39 33 38 2c 510,42035,21938,
1ad0: 33 33 38 35 34 2c 32 35 30 31 35 2c 35 36 35 34 33854,25015,5654
1ae0: 37 2c 35 35 31 38 35 2c 39 32 33 34 34 2c 34 31 7,55185,92344,41
1af0: 35 31 35 2c 39 30 39 33 35 2c 31 39 31 38 32 2c 515,90935,19182,
1b00: 36 36 37 30 34 2c 38 33 30 37 32 2c 32 31 37 33 66704,83072,2173
1b10: 31 2c 36 34 35 34 33 2c 31 37 34 39 38 2c 35 38 1,64543,17498,58
1b20: 36 31 2c 31 33 32 37 34 2c 31 30 34 34 38 2c 38 61,13274,10448,8
1b30: 30 36 32 38 2c 33 36 33 31 31 2c 31 30 38 35 35 0628,36311,10855
1b40: 2c 35 37 37 38 36 2c 39 39 35 39 33 2c 38 32 32 ,57786,99593,822
1b50: 32 35 2c 33 36 35 34 36 2c 36 33 37 37 32 2c 37 25,36546,63772,7
1b60: 34 35 39 32 2c 33 33 37 36 2c 31 36 30 37 30 2c 4592,3376,16070,
1b70: 38 39 30 37 34 2c 34 36 30 36 37 2c 32 37 35 35 89074,46067,2755
1b80: 31 2c 32 37 33 31 2c 36 36 36 31 38 2c 38 39 36 1,2731,66618,896
1b90: 38 33 2c 36 32 33 38 38 2c 39 36 38 31 2c 34 38 83,62388,9681,48
1ba0: 31 38 36 2c 36 31 39 33 36 2c 38 30 33 33 33 2c 186,61936,80333,
1bb0: 32 31 33 39 32 2c 32 37 34 34 38 2c 31 35 39 32 21392,27448,1592
1bc0: 30 2c 39 32 32 37 34 2c 35 31 36 34 35 2c 34 30 0,92274,51645,40
1bd0: 36 39 35 2c 33 32 34 39 31 2c 33 39 38 38 37 2c 695,32491,39887,
1be0: 34 31 35 34 35 2c 39 30 35 34 34 2c 38 35 31 33 41545,90544,8513
1bf0: 38 2c 35 37 34 35 34 2c 39 31 30 33 32 2c 36 39 8,57454,91032,69
1c00: 32 37 34 2c 36 30 35 32 30 2c 36 38 34 34 34 2c 274,60520,68444,
1c10: 32 32 39 34 39 2c 35 34 35 33 33 2c 31 39 39 32 22949,54533,1992
1c20: 30 2c 39 36 32 39 37 2c 39 33 35 33 30 2c 37 31 0,96297,93530,71
1c30: 39 33 36 2c 32 33 37 32 31 2c 31 36 36 33 30 2c 936,23721,16630,
1c40: 39 37 32 35 30 2c 32 36 39 31 38 2c 34 30 37 38 97250,26918,4078
1c50: 2c 33 31 35 34 37 2c 32 32 39 34 32 2c 39 38 34 ,31547,22942,984
1c60: 37 33 2c 32 31 35 30 33 2c 39 36 37 37 32 2c 35 73,21503,96772,5
1c70: 35 31 33 33 2c 37 39 34 38 36 2c 31 33 37 30 37 5133,79486,13707
1c80: 2c 31 34 32 30 38 2c 34 32 36 35 34 2c 36 31 35 ,14208,42654,615
1c90: 31 32 2c 33 38 33 36 34 2c 36 30 39 35 2c 31 33 12,38364,6095,13
1ca0: 38 30 38 2c 31 31 31 38 39 2c 36 34 37 30 39 2c 808,11189,64709,
1cb0: 31 32 37 37 2c 39 39 38 32 34 2c 37 36 39 37 33 1277,99824,76973
1cc0: 2c 34 38 39 39 38 2c 31 39 36 30 33 2c 31 32 38 ,48998,19603,128
1cd0: 39 31 2c 37 35 39 33 2c 38 39 30 32 39 2c 36 36 91,7593,89029,66
1ce0: 39 38 37 2c 34 34 34 34 38 2c 38 33 37 37 39 2c 987,44448,83779,
1cf0: 38 35 34 37 39 2c 31 36 31 33 34 2c 32 33 39 38 85479,16134,2398
1d00: 30 2c 33 33 39 33 36 2c 38 35 34 34 34 2c 39 38 0,33936,85444,98
1d10: 32 33 35 2c 32 31 31 31 35 2c 34 31 34 32 33 2c 235,21115,41423,
1d20: 35 38 33 34 33 2c 38 36 38 30 39 2c 31 32 36 35 58343,86809,1265
1d30: 30 2c 38 30 30 32 32 2c 31 31 32 35 33 2c 39 36 0,80022,11253,96
1d40: 39 34 32 2c 32 35 35 32 2c 36 33 33 30 33 2c 36 942,2552,63303,6
1d50: 31 37 30 32 2c 39 33 39 38 38 2c 31 32 38 37 34 1702,93988,12874
1d60: 2c 31 39 35 30 37 2c 34 37 35 33 39 2c 31 30 36 ,19507,47539,106
1d70: 32 33 2c 38 30 39 31 33 2c 39 33 37 32 34 2c 36 23,80913,93724,6
1d80: 36 39 38 2c 37 38 34 30 37 2c 38 34 36 32 36 2c 698,78407,84626,
1d90: 31 39 39 35 35 2c 39 34 35 35 34 2c 31 38 39 30 19955,94554,1890
1da0: 38 2c 31 37 35 33 34 2c 37 38 31 35 2c 34 39 31 8,17534,7815,491
1db0: 33 33 2c 38 36 31 39 36 2c 31 34 32 32 33 2c 35 33,86196,14223,5
1dc0: 39 39 34 30 2c 34 39 35 32 35 2c 35 32 31 37 34 9940,49525,52174
1dd0: 2c 38 33 31 39 38 2c 38 31 39 33 31 2c 39 30 35 ,83198,81931,905
1de0: 31 38 2c 37 33 38 34 39 2c 34 38 35 31 34 2c 31 18,73849,48514,1
1df0: 34 38 36 2c 36 34 38 39 37 2c 31 36 37 39 31 2c 486,64897,16791,
1e00: 37 33 35 30 39 2c 38 33 30 36 31 2c 34 31 31 30 73509,83061,4110
1e10: 31 2c 32 34 33 33 39 2c 34 30 39 31 31 2c 35 32 1,24339,40911,52
1e20: 30 34 32 2c 34 31 35 36 35 2c 31 32 30 31 30 2c 042,41565,12010,
1e30: 31 36 38 31 30 2c 39 31 34 36 34 2c 37 32 39 37 16810,91464,7297
1e40: 39 2c 34 32 31 39 36 2c 32 31 31 32 37 2c 37 35 9,42196,21127,75
1e50: 34 33 35 2c 31 39 33 33 30 2c 34 32 31 32 30 2c 435,19330,42120,
1e60: 31 32 35 32 36 2c 32 34 34 30 30 2c 33 35 38 36 12526,24400,3586
1e70: 32 2c 34 36 35 35 32 2c 36 38 31 35 37 2c 36 35 2,46552,68157,65
1e80: 33 33 35 2c 37 35 37 31 33 2c 31 37 32 34 33 2c 335,75713,17243,
1e90: 39 35 31 32 34 2c 39 36 31 31 34 2c 31 35 36 37 95124,96114,1567
1ea0: 30 2c 32 35 39 34 35 2c 32 39 37 38 36 2c 36 38 0,25945,29786,68
1eb0: 34 34 38 2c 31 38 33 31 34 2c 39 32 36 34 37 2c 448,18314,92647,
1ec0: 35 37 37 30 32 2c 38 37 33 30 34 2c 31 35 37 37 57702,87304,1577
1ed0: 39 2c 33 38 35 36 32 2c 33 33 33 34 30 2c 34 30 9,38562,33340,40
1ee0: 31 39 33 2c 33 39 37 36 38 2c 33 37 35 31 31 2c 193,39768,37511,
1ef0: 36 35 34 30 35 2c 33 37 32 37 32 2c 34 33 35 39 65405,37272,4359
1f00: 37 2c 31 36 33 31 34 2c 35 37 30 31 30 2c 33 37 7,16314,57010,37
1f10: 33 35 39 2c 31 31 35 34 39 2c 35 33 33 38 38 2c 359,11549,53388,
1f20: 33 39 35 38 33 2c 34 39 37 31 36 2c 39 35 37 32 39583,49716,9572
1f30: 35 2c 31 35 34 36 34 2c 32 30 31 31 33 2c 31 30 5,15464,20113,10
1f40: 33 36 32 2c 39 38 32 32 2c 38 38 32 30 39 2c 34 362,9822,88209,4
1f50: 34 36 30 34 2c 35 34 39 32 37 2c 32 30 36 38 38 4604,54927,20688
1f60: 2c 31 37 36 38 34 2c 31 33 35 32 36 2c 33 36 30 ,17684,13526,360
1f70: 38 31 2c 33 30 33 39 39 2c 33 35 39 35 35 2c 31 81,30399,35955,1
1f80: 30 37 37 35 2c 38 30 33 36 32 2c 35 36 37 33 35 0775,80362,56735
1f90: 2c 36 39 32 38 35 2c 38 37 37 36 34 2c 38 30 38 ,69285,87764,808
1fa0: 36 2c 39 36 38 36 36 2c 36 34 39 31 39 2c 34 31 6,96866,64919,41
1fb0: 31 32 35 2c 35 30 38 36 39 2c 33 39 37 33 30 2c 125,50869,39730,
1fc0: 38 35 30 32 31 2c 32 33 32 36 35 2c 37 34 37 32 85021,23265,7472
1fd0: 2c 30 20 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 ,0 };... vector
1fe0: 20 3c 69 6e 74 3e 20 72 6f 73 65 73 28 72 6f 73 <int> roses(ros
1ff0: 65 73 5f 2c 20 72 6f 73 65 73 5f 2b 73 69 7a 65 es_, roses_+size
2000: 6f 66 28 72 6f 73 65 73 5f 29 2f 73 69 7a 65 6f of(roses_)/sizeo
2010: 66 28 2a 72 6f 73 65 73 5f 29 29 3b 20 0d 0a 09 f(*roses_)); ...
2020: 69 6e 74 20 74 75 6c 69 70 73 5f 5b 5d 20 3d 20 int tulips_[] =
2030: 7b 20 30 2c 39 37 36 39 2c 33 30 32 38 2c 38 35 { 0,9769,3028,85
2040: 32 30 39 2c 33 31 35 32 32 2c 32 39 35 33 37 2c 209,31522,29537,
2050: 31 35 36 37 30 2c 39 38 37 32 2c 37 34 31 35 32 15670,9872,74152
2060: 2c 39 30 35 31 31 2c 33 30 35 35 32 2c 38 35 39 ,90511,30552,859
2070: 34 37 2c 34 38 34 30 37 2c 36 33 31 30 39 2c 38 47,48407,63109,8
2080: 36 36 31 2c 37 38 39 37 31 2c 39 38 36 35 30 2c 661,78971,98650,
2090: 31 31 34 34 37 2c 31 36 35 39 37 2c 35 32 37 36 11447,16597,5276
20a0: 38 2c 35 37 39 39 38 2c 36 32 34 35 39 2c 39 37 8,57998,62459,97
20b0: 33 35 33 2c 34 36 32 39 30 2c 39 39 35 35 36 2c 353,46290,99556,
20c0: 36 35 33 31 35 2c 32 39 36 34 32 2c 36 35 32 30 65315,29642,6520
20d0: 39 2c 35 31 38 36 2c 36 35 37 35 2c 31 33 39 39 9,5186,6575,1399
20e0: 36 2c 37 38 32 35 33 2c 38 35 33 36 39 2c 32 37 6,78253,85369,27
20f0: 36 34 34 2c 32 30 33 30 37 2c 38 35 39 36 33 2c 644,20307,85963,
2100: 34 32 30 32 34 2c 37 37 30 34 2c 31 33 34 39 35 42024,7704,13495
2110: 2c 39 37 33 33 37 2c 32 33 36 38 31 2c 36 35 33 ,97337,23681,653
2120: 32 2c 35 31 34 35 38 2c 36 33 31 34 38 2c 37 34 2,51458,63148,74
2130: 32 35 31 2c 31 37 33 31 32 2c 39 34 36 34 30 2c 251,17312,94640,
2140: 33 37 37 36 33 2c 35 31 32 38 34 2c 39 33 39 32 37763,51284,9392
2150: 30 2c 32 30 38 30 37 2c 35 32 37 38 38 2c 35 34 0,20807,52788,54
2160: 30 32 32 2c 37 33 38 36 33 2c 32 36 33 38 34 2c 022,73863,26384,
2170: 35 37 34 38 36 2c 39 35 37 32 33 2c 36 33 39 31 57486,95723,6391
2180: 33 2c 34 37 39 36 2c 37 39 35 32 2c 31 30 34 30 3,4796,7952,1040
2190: 31 2c 35 37 30 38 36 2c 39 34 30 33 30 2c 36 30 1,57086,94030,60
21a0: 35 34 34 2c 38 33 34 39 38 2c 33 39 35 33 2c 33 544,83498,3953,3
21b0: 33 35 31 38 2c 36 34 30 37 32 2c 35 30 33 39 31 3518,64072,50391
21c0: 2c 36 35 34 33 30 2c 32 32 32 36 30 2c 39 37 35 ,65430,22260,975
21d0: 33 36 2c 38 34 39 39 2c 39 35 33 37 32 2c 35 36 36,8499,95372,56
21e0: 36 32 33 2c 31 35 34 31 31 2c 34 30 38 34 35 2c 623,15411,40845,
21f0: 33 31 38 36 39 2c 32 32 37 34 38 2c 34 30 32 35 31869,22748,4025
2200: 39 2c 31 31 37 33 31 2c 33 34 39 38 38 2c 35 30 9,11731,34988,50
2210: 30 37 2c 31 36 37 32 39 2c 31 30 34 32 39 2c 37 07,16729,10429,7
2220: 36 34 39 2c 32 35 35 32 37 2c 35 37 35 39 38 2c 649,25527,57598,
2230: 39 30 31 35 34 2c 35 32 32 38 34 2c 33 32 36 37 90154,52284,3267
2240: 38 2c 35 31 33 33 34 2c 32 33 36 32 37 2c 32 38 8,51334,23627,28
2250: 30 33 31 2c 32 34 35 32 33 2c 31 37 33 30 31 2c 031,24523,17301,
2260: 32 38 33 37 35 2c 35 36 34 34 36 2c 32 34 38 30 28375,56446,2480
2270: 34 2c 39 37 32 32 34 2c 37 30 37 33 2c 34 32 33 4,97224,7073,423
2280: 30 35 2c 33 36 38 36 33 2c 35 38 33 36 34 2c 38 05,36863,58364,8
2290: 39 34 36 35 2c 32 32 35 31 34 2c 36 34 39 33 34 9465,22514,64934
22a0: 2c 35 31 38 33 33 2c 36 39 34 33 32 2c 31 35 31 ,51833,69432,151
22b0: 34 34 2c 34 31 31 34 2c 31 39 31 33 30 2c 35 38 44,4114,19130,58
22c0: 32 33 31 2c 35 36 39 34 37 2c 31 30 36 39 37 2c 231,56947,10697,
22d0: 38 39 37 37 34 2c 32 37 33 35 33 2c 34 35 38 32 89774,27353,4582
22e0: 2c 39 38 38 37 37 2c 31 36 36 31 31 2c 34 38 39 ,98877,16611,489
22f0: 38 2c 33 36 32 32 37 2c 36 39 33 31 39 2c 31 30 8,36227,69319,10
2300: 31 34 35 2c 38 30 32 31 2c 39 31 32 33 36 2c 37 145,8021,91236,7
2310: 38 32 32 36 2c 36 38 31 36 34 2c 32 34 33 30 34 8226,68164,24304
2320: 2c 33 38 39 30 32 2c 39 39 30 34 39 2c 35 35 35 ,38902,99049,555
2330: 36 33 2c 31 35 36 36 37 2c 38 39 33 33 39 2c 35 63,15667,89339,5
2340: 33 35 34 32 2c 35 35 35 32 38 2c 35 36 36 34 38 3542,55528,56648
2350: 2c 38 33 38 34 31 2c 33 34 33 36 39 2c 38 33 35 ,83841,34369,835
2360: 30 37 2c 31 30 33 32 32 2c 35 34 30 36 36 2c 32 07,10322,54066,2
2370: 31 30 39 2c 33 38 36 39 31 2c 35 34 30 36 38 2c 109,38691,54068,
2380: 34 31 34 36 2c 33 34 35 37 38 2c 31 30 35 33 39 4146,34578,10539
2390: 2c 33 39 38 32 35 2c 35 33 30 30 38 2c 33 38 31 ,39825,53008,381
23a0: 31 35 2c 37 36 39 37 37 2c 38 32 31 32 38 2c 33 15,76977,82128,3
23b0: 36 32 35 30 2c 37 39 36 34 30 2c 36 32 38 37 36 6250,79640,62876
23c0: 2c 36 30 32 32 34 2c 38 32 34 35 38 2c 32 30 36 ,60224,82458,206
23d0: 37 32 2c 37 34 30 32 37 2c 31 33 30 31 35 2c 31 72,74027,13015,1
23e0: 37 33 33 36 2c 34 30 30 32 32 2c 39 34 36 36 2c 7336,40022,9466,
23f0: 31 36 31 39 30 2c 39 35 32 30 31 2c 31 39 38 34 16190,95201,1984
2400: 2c 37 31 34 33 39 2c 33 31 36 32 32 2c 38 36 33 ,71439,31622,863
2410: 30 34 2c 32 31 32 33 38 2c 37 37 36 38 31 2c 34 04,21238,77681,4
2420: 32 37 39 33 2c 35 38 33 34 37 2c 36 34 35 34 35 2793,58347,64545
2430: 2c 38 34 36 31 2c 36 31 31 39 38 2c 36 31 34 36 ,8461,61198,6146
2440: 32 2c 31 37 33 35 31 2c 31 31 31 39 39 2c 37 36 2,17351,11199,76
2450: 33 38 38 2c 38 38 30 32 34 2c 37 31 35 31 2c 36 388,88024,7151,6
2460: 34 37 31 35 2c 34 33 35 30 38 2c 38 36 31 37 36 4715,43508,86176
2470: 2c 31 36 39 38 38 2c 31 32 38 32 33 2c 36 30 33 ,16988,12823,603
2480: 35 38 2c 36 35 39 33 30 2c 31 39 32 37 30 2c 39 58,65930,19270,9
2490: 33 30 39 30 2c 37 36 35 34 31 2c 33 35 34 34 36 3090,76541,35446
24a0: 2c 38 31 33 32 31 2c 33 33 37 33 36 2c 37 38 34 ,81321,33736,784
24b0: 33 39 2c 35 35 37 31 34 2c 31 35 30 39 30 2c 34 39,55714,15090,4
24c0: 30 33 35 35 2c 32 36 36 35 35 2c 34 39 38 31 39 0355,26655,49819
24d0: 2c 39 34 34 31 31 2c 34 34 39 35 36 2c 38 37 34 ,94411,44956,874
24e0: 39 38 2c 34 32 31 30 34 2c 31 36 39 39 39 2c 37 98,42104,16999,7
24f0: 30 33 31 39 2c 32 35 38 31 32 2c 34 34 35 39 39 0319,25812,44599
2500: 2c 35 32 31 36 37 2c 36 38 39 37 38 2c 36 37 34 ,52167,68978,674
2510: 33 35 2c 31 39 34 39 37 2c 35 37 30 33 32 2c 31 35,19497,57032,1
2520: 35 39 33 35 2c 31 32 37 39 30 2c 38 37 34 31 31 5935,12790,87411
2530: 2c 31 32 33 31 31 2c 32 38 37 34 36 2c 32 34 35 ,12311,28746,245
2540: 35 35 2c 37 32 31 32 31 2c 38 36 35 30 33 2c 31 55,72121,86503,1
2550: 31 30 39 37 2c 38 32 38 33 30 2c 33 32 34 30 30 1097,82830,32400
2560: 2c 36 37 38 37 31 2c 33 33 31 37 31 2c 33 31 37 ,67871,33171,317
2570: 32 30 2c 32 37 37 35 2c 33 31 38 31 34 2c 32 39 20,2775,31814,29
2580: 31 34 39 2c 34 38 30 38 34 2c 34 37 30 35 34 2c 149,48084,47054,
2590: 32 39 35 38 31 2c 35 38 31 35 38 2c 31 36 30 33 29581,58158,1603
25a0: 32 2c 35 33 32 39 39 2c 35 35 31 36 32 2c 34 32 2,53299,55162,42
25b0: 39 34 33 2c 39 33 35 32 38 2c 33 34 38 37 38 2c 943,93528,34878,
25c0: 38 36 34 36 35 2c 33 34 32 37 31 2c 31 37 34 30 86465,34271,1740
25d0: 30 2c 33 33 30 37 2c 33 35 36 30 34 2c 32 30 36 0,3307,35604,206
25e0: 37 30 2c 38 37 39 39 35 2c 39 32 32 38 38 2c 31 70,87995,92288,1
25f0: 30 31 36 35 2c 37 34 35 39 2c 37 36 38 33 34 2c 0165,7459,76834,
2600: 36 34 39 32 36 2c 36 36 34 31 38 2c 31 35 36 37 64926,66418,1567
2610: 31 2c 35 35 38 32 39 2c 37 36 31 35 34 2c 35 39 1,55829,76154,59
2620: 38 34 33 2c 31 35 31 38 34 2c 38 33 34 34 35 2c 843,15184,83445,
2630: 32 38 32 39 35 2c 39 34 34 31 37 2c 35 36 31 37 28295,94417,5617
2640: 33 2c 36 30 31 38 35 2c 34 34 31 35 33 2c 33 35 3,60185,44153,35
2650: 37 32 31 2c 31 35 38 31 39 2c 32 33 35 32 31 2c 721,15819,23521,
2660: 36 31 35 37 33 2c 34 36 30 36 30 2c 37 33 38 31 61573,46060,7381
2670: 36 2c 34 37 38 31 31 2c 39 38 38 30 38 2c 32 30 6,47811,98808,20
2680: 37 37 2c 39 38 31 34 32 2c 36 34 33 35 38 2c 31 77,98142,64358,1
2690: 36 30 39 38 2c 37 30 33 32 37 2c 35 32 38 31 31 6098,70327,52811
26a0: 2c 38 34 39 31 37 2c 38 31 37 35 31 2c 36 35 30 ,84917,81751,650
26b0: 31 38 2c 38 31 35 36 38 2c 33 30 38 39 35 2c 39 18,81568,30895,9
26c0: 38 33 37 30 2c 37 33 31 35 33 2c 36 30 39 30 38 8370,73153,60908
26d0: 2c 30 20 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 ,0 };... vector
26e0: 20 3c 69 6e 74 3e 20 74 75 6c 69 70 73 28 74 75 <int> tulips(tu
26f0: 6c 69 70 73 5f 2c 20 74 75 6c 69 70 73 5f 2b 73 lips_, tulips_+s
2700: 69 7a 65 6f 66 28 74 75 6c 69 70 73 5f 29 2f 73 izeof(tulips_)/s
2710: 69 7a 65 6f 66 28 2a 74 75 6c 69 70 73 5f 29 29 izeof(*tulips_))
2720: 3b 20 0d 0a 09 69 6e 74 20 63 6f 73 74 73 5f 5b ; ...int costs_[
2730: 5d 20 3d 20 7b 20 30 2c 36 36 36 32 36 2c 37 31 ] = { 0,66626,71
2740: 34 36 39 2c 37 30 33 32 38 2c 36 32 30 39 32 2c 469,70328,62092,
2750: 31 38 35 31 36 2c 37 31 34 35 33 2c 38 39 34 31 18516,71453,8941
2760: 2c 39 34 38 34 30 2c 35 36 35 31 30 2c 36 38 30 ,94840,56510,680
2770: 39 31 2c 39 36 37 30 38 2c 38 39 30 37 32 2c 32 91,96708,89072,2
2780: 30 38 34 37 2c 33 37 31 34 2c 37 31 30 38 31 2c 0847,3714,71081,
2790: 38 39 37 39 30 2c 32 38 36 36 38 2c 38 36 35 33 89790,28668,8653
27a0: 37 2c 31 30 31 37 34 2c 34 32 37 35 36 2c 31 35 7,10174,42756,15
27b0: 36 37 36 2c 37 39 35 39 36 2c 39 30 39 31 34 2c 676,79596,90914,
27c0: 35 30 39 36 36 2c 32 30 37 37 34 2c 36 30 37 34 50966,20774,6074
27d0: 39 2c 36 34 37 32 32 2c 34 37 36 38 32 2c 38 33 9,64722,47682,83
27e0: 32 34 35 2c 37 31 33 33 39 2c 36 32 37 36 32 2c 245,71339,62762,
27f0: 38 36 31 36 38 2c 34 34 36 37 2c 33 37 35 35 36 86168,4467,37556
2800: 2c 36 34 30 36 37 2c 38 36 39 37 34 2c 36 38 32 ,64067,86974,682
2810: 32 32 2c 36 37 35 38 30 2c 34 33 31 39 39 2c 38 22,67580,43199,8
2820: 34 38 34 37 2c 39 36 36 33 31 2c 39 37 33 37 39 4847,96631,97379
2830: 2c 39 32 34 31 39 2c 39 37 30 38 38 2c 37 32 33 ,92419,97088,723
2840: 35 33 2c 36 36 30 38 38 2c 36 35 38 37 30 2c 36 53,66088,65870,6
2850: 32 39 39 2c 38 30 33 30 37 2c 35 38 30 38 36 2c 299,80307,58086,
2860: 35 31 37 38 39 2c 32 36 36 36 30 2c 37 30 33 30 51789,26660,7030
2870: 38 2c 36 34 39 33 38 2c 35 38 34 30 39 2c 38 39 8,64938,58409,89
2880: 31 32 37 2c 33 31 35 33 37 2c 37 30 31 38 38 2c 127,31537,70188,
2890: 33 35 31 32 32 2c 34 36 38 32 31 2c 34 35 39 36 35122,46821,4596
28a0: 36 2c 31 39 37 37 32 2c 34 30 31 33 38 2c 33 32 6,19772,40138,32
28b0: 36 32 39 2c 35 36 31 30 2c 36 34 39 35 38 2c 36 629,5610,64958,6
28c0: 34 37 31 30 2c 37 37 37 37 36 2c 35 30 38 35 31 4710,77776,50851
28d0: 2c 33 38 38 31 31 2c 37 32 37 30 36 2c 33 37 31 ,38811,72706,371
28e0: 30 35 2c 36 35 32 38 31 2c 36 37 36 30 37 2c 39 05,65281,67607,9
28f0: 39 36 30 33 2c 34 30 35 35 2c 33 37 31 32 34 2c 9603,4055,37124,
2900: 32 36 37 31 37 2c 31 30 39 38 37 2c 37 36 33 33 26717,10987,7633
2910: 34 2c 38 38 39 36 31 2c 33 31 39 36 31 2c 36 39 4,88961,31961,69
2920: 35 35 33 2c 39 35 33 33 39 2c 33 32 32 35 2c 37 553,95339,3225,7
2930: 33 37 34 36 2c 31 36 32 32 37 2c 38 34 30 34 30 3746,16227,84040
2940: 2c 39 35 36 30 36 2c 38 38 39 33 34 2c 31 34 33 ,95606,88934,143
2950: 39 34 2c 36 32 32 34 2c 32 30 32 31 33 2c 31 35 94,6224,20213,15
2960: 36 39 30 2c 39 39 36 37 2c 39 37 31 35 36 2c 32 690,9967,97156,2
2970: 37 33 31 32 2c 31 34 31 31 32 2c 34 35 38 31 34 7312,14112,45814
2980: 2c 39 33 38 33 37 2c 37 34 39 33 37 2c 31 34 35 ,93837,74937,145
2990: 38 38 2c 32 33 36 37 31 2c 33 37 31 37 33 2c 39 88,23671,37173,9
29a0: 39 39 30 39 2c 39 30 33 32 32 2c 38 39 39 32 2c 9909,90322,8992,
29b0: 34 31 36 33 32 2c 38 30 36 39 35 2c 32 30 39 37 41632,80695,2097
29c0: 31 2c 33 35 32 34 35 2c 38 35 36 31 33 2c 33 35 1,35245,85613,35
29d0: 33 34 37 2c 34 35 36 38 30 2c 38 36 35 35 39 2c 347,45680,86559,
29e0: 37 30 39 38 37 2c 35 31 37 36 37 2c 34 37 33 35 70987,51767,4735
29f0: 34 2c 39 30 33 38 33 2c 35 30 39 39 2c 35 35 36 4,90383,5099,556
2a00: 33 35 2c 35 36 35 34 35 2c 39 37 36 31 34 2c 32 35,56545,97614,2
2a10: 38 39 33 33 2c 36 37 35 38 39 2c 32 33 36 37 37 8933,67589,23677
2a20: 2c 36 39 35 38 36 2c 38 36 37 37 34 2c 37 30 35 ,69586,86774,705
2a30: 37 33 2c 33 39 35 30 39 2c 37 37 32 38 32 2c 38 73,39509,77282,8
2a40: 39 35 36 34 2c 37 38 31 37 2c 35 36 39 37 30 2c 9564,7817,56970,
2a50: 34 39 35 30 33 2c 34 39 37 33 34 2c 34 38 34 31 49503,49734,4841
2a60: 35 2c 36 39 35 32 38 2c 39 38 36 36 2c 35 32 31 5,69528,9866,521
2a70: 36 35 2c 34 30 39 37 34 2c 36 30 34 36 39 2c 37 65,40974,60469,7
2a80: 35 32 37 30 2c 35 36 30 36 2c 34 30 37 30 2c 38 5270,5606,4070,8
2a90: 36 32 34 39 2c 33 30 35 35 33 2c 34 33 32 33 34 6249,30553,43234
2aa0: 2c 39 37 30 31 35 2c 39 39 35 37 33 2c 32 33 35 ,97015,99573,235
2ab0: 36 39 2c 31 35 38 33 32 2c 36 36 33 39 36 2c 31 69,15832,66396,1
2ac0: 32 31 37 39 2c 32 31 34 32 36 2c 39 32 31 36 37 2179,21426,92167
2ad0: 2c 35 36 31 31 35 2c 34 36 38 33 38 2c 35 39 31 ,56115,46838,591
2ae0: 30 35 2c 34 35 33 36 31 2c 35 34 39 36 38 2c 33 05,45361,54968,3
2af0: 35 31 34 31 2c 35 39 32 39 32 2c 32 32 36 32 2c 5141,59292,2262,
2b00: 31 30 30 33 35 2c 37 36 38 39 33 2c 32 30 33 33 10035,76893,2033
2b10: 31 2c 33 35 39 30 30 2c 32 32 34 35 39 2c 36 34 1,35900,22459,64
2b20: 39 34 30 2c 39 37 31 36 32 2c 36 37 34 38 31 2c 940,97162,67481,
2b30: 32 33 35 30 35 2c 33 34 37 34 36 2c 38 35 30 30 23505,34746,8500
2b40: 34 2c 31 39 35 31 2c 33 34 32 35 38 2c 34 33 33 4,1951,34258,433
2b50: 32 33 2c 32 38 36 32 35 2c 37 34 34 34 38 2c 35 23,28625,74448,5
2b60: 36 37 30 32 2c 36 35 35 31 30 2c 35 30 39 32 31 6702,65510,50921
2b70: 2c 36 33 36 35 2c 31 35 35 33 38 2c 34 31 31 34 ,6365,15538,4114
2b80: 31 2c 37 38 35 30 39 2c 36 30 39 35 33 2c 37 39 1,78509,60953,79
2b90: 34 34 32 2c 37 33 33 33 31 2c 39 30 36 30 31 2c 442,73331,90601,
2ba0: 32 31 31 39 32 2c 39 34 35 33 33 2c 33 37 39 39 21192,94533,3799
2bb0: 31 2c 31 37 31 32 35 2c 33 39 33 32 30 2c 37 32 1,17125,39320,72
2bc0: 36 36 33 2c 32 37 33 30 32 2c 39 37 39 30 32 2c 663,27302,97902,
2bd0: 39 36 37 39 31 2c 38 38 33 36 31 2c 39 37 32 32 96791,88361,9722
2be0: 33 2c 32 39 32 35 32 2c 34 34 36 31 35 2c 32 30 3,29252,44615,20
2bf0: 35 34 39 2c 34 32 33 36 37 2c 38 35 38 37 36 2c 549,42367,85876,
2c00: 34 37 32 37 30 2c 36 38 31 37 36 2c 32 37 36 34 47270,68176,2764
2c10: 2c 35 31 38 31 38 2c 37 36 37 36 33 2c 33 33 35 ,51818,76763,335
2c20: 32 36 2c 32 33 33 38 37 2c 34 37 36 34 33 2c 32 26,23387,47643,2
2c30: 33 33 35 30 2c 32 38 31 36 36 2c 37 36 34 39 30 3350,28166,76490
2c40: 2c 38 30 33 37 37 2c 32 32 31 38 31 2c 36 33 30 ,80377,22181,630
2c50: 31 2c 37 35 33 31 36 2c 36 35 38 33 36 2c 38 39 1,75316,65836,89
2c60: 38 31 33 2c 32 30 39 30 38 2c 39 34 37 37 37 2c 813,20908,94777,
2c70: 32 38 34 34 31 2c 35 38 39 31 31 2c 32 37 39 30 28441,58911,2790
2c80: 30 2c 33 36 31 30 39 2c 37 30 36 31 31 2c 34 32 0,36109,70611,42
2c90: 34 33 38 2c 39 31 34 37 37 2c 36 34 37 37 30 2c 438,91477,64770,
2ca0: 31 37 35 37 39 2c 34 34 30 38 38 2c 34 37 34 38 17579,44088,4748
2cb0: 32 2c 36 30 33 39 34 2c 35 39 35 33 38 2c 32 30 2,60394,59538,20
2cc0: 34 38 37 2c 37 30 30 30 39 2c 34 32 35 33 39 2c 487,70009,42539,
2cd0: 39 31 37 36 32 2c 37 37 36 33 37 2c 37 35 39 35 91762,77637,7595
2ce0: 39 2c 39 30 32 39 32 2c 34 35 33 31 36 2c 35 30 9,90292,45316,50
2cf0: 30 38 33 2c 33 31 37 38 33 2c 36 33 37 31 33 2c 083,31783,63713,
2d00: 33 34 30 2c 33 30 38 33 32 2c 32 31 36 36 32 2c 340,30832,21662,
2d10: 31 33 37 35 32 2c 38 34 35 32 35 2c 39 36 32 32 13752,84525,9622
2d20: 36 2c 34 30 39 38 31 2c 33 37 33 33 39 2c 36 36 6,40981,37339,66
2d30: 38 31 2c 36 39 38 39 38 2c 34 33 38 30 30 2c 34 81,69898,43800,4
2d40: 32 36 34 33 2c 34 35 39 32 38 2c 34 31 31 30 36 2643,45928,41106
2d50: 2c 34 32 39 36 30 2c 32 33 30 31 37 2c 38 39 36 ,42960,23017,896
2d60: 35 36 2c 38 32 37 34 30 2c 33 38 33 31 35 2c 36 56,82740,38315,6
2d70: 36 39 31 37 2c 36 34 37 30 39 2c 38 35 39 32 38 6917,64709,85928
2d80: 2c 36 36 33 37 35 2c 35 30 33 32 31 2c 34 31 36 ,66375,50321,416
2d90: 35 39 2c 39 31 38 32 36 2c 38 31 32 31 31 2c 36 59,91826,81211,6
2da0: 33 31 34 39 2c 37 33 33 36 34 2c 31 38 32 39 39 3149,73364,18299
2db0: 2c 35 30 38 33 35 2c 32 37 33 38 32 2c 37 30 35 ,50835,27382,705
2dc0: 30 2c 35 36 35 35 32 2c 34 36 38 37 36 2c 33 34 0,56552,46876,34
2dd0: 35 38 39 2c 32 30 38 35 33 2c 30 20 7d 3b 0d 0a 589,20853,0 };..
2de0: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
2df0: 63 6f 73 74 73 28 63 6f 73 74 73 5f 2c 20 63 6f costs(costs_, co
2e00: 73 74 73 5f 2b 73 69 7a 65 6f 66 28 63 6f 73 74 sts_+sizeof(cost
2e10: 73 5f 29 2f 73 69 7a 65 6f 66 28 2a 63 6f 73 74 s_)/sizeof(*cost
2e20: 73 5f 29 29 3b 20 0d 0a 09 20 20 64 6f 75 62 6c s_)); ... doubl
2e30: 65 20 5f 20 3d 20 2d 32 3b 0d 0a 45 4e 44 0d 0a e _ = -2;..END..
2e40: 2f 2a 0d 0a 43 41 53 45 28 36 29 0d 0a 09 69 6e /*..CASE(6)...in
2e50: 74 20 52 20 3d 20 35 3b 20 0d 0a 09 69 6e 74 20 t R = 5; ...int
2e60: 43 20 3d 20 36 30 3b 20 0d 0a 09 69 6e 74 20 4b C = 60; ...int K
2e70: 20 3d 20 31 30 30 30 30 30 30 30 30 3b 20 0d 0a = 100000000; ..
2e80: 09 69 6e 74 20 72 6f 73 65 73 5f 5b 5d 20 3d 20 .int roses_[] =
2e90: 7b 20 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c { 1,1,1,1,1,1,1,
2ea0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
2eb0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
2ec0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
2ed0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
2ee0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
2ef0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
2f00: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
2f10: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
2f20: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
2f30: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
2f40: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
2f50: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
2f60: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
2f70: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
2f80: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
2f90: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
2fa0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
2fb0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
2fc0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
2fd0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
2fe0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
2ff0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3000: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3010: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3020: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3030: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3040: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3050: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3060: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3070: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3080: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3090: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
30a0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
30b0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
30c0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
30d0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
30e0: 31 2c 31 2c 31 2c 31 2c 31 20 7d 3b 0d 0a 09 20 1,1,1,1,1 };...
30f0: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 72 6f vector <int> ro
3100: 73 65 73 28 72 6f 73 65 73 5f 2c 20 72 6f 73 65 ses(roses_, rose
3110: 73 5f 2b 73 69 7a 65 6f 66 28 72 6f 73 65 73 5f s_+sizeof(roses_
3120: 29 2f 73 69 7a 65 6f 66 28 2a 72 6f 73 65 73 5f )/sizeof(*roses_
3130: 29 29 3b 20 0d 0a 09 69 6e 74 20 74 75 6c 69 70 )); ...int tulip
3140: 73 5f 5b 5d 20 3d 20 7b 20 31 2c 31 2c 31 2c 31 s_[] = { 1,1,1,1
3150: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3160: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3170: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3180: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3190: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
31a0: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
31b0: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
31c0: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
31d0: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
31e0: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
31f0: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3200: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3210: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3220: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3230: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3240: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3250: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3260: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3270: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3280: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3290: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
32a0: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
32b0: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
32c0: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
32d0: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
32e0: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
32f0: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3300: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3310: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3320: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3330: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3340: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3350: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3360: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3370: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3380: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
3390: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 ,1,1,1,1,1,1,1,1
33a0: 20 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c };... vector <
33b0: 69 6e 74 3e 20 74 75 6c 69 70 73 28 74 75 6c 69 int> tulips(tuli
33c0: 70 73 5f 2c 20 74 75 6c 69 70 73 5f 2b 73 69 7a ps_, tulips_+siz
33d0: 65 6f 66 28 74 75 6c 69 70 73 5f 29 2f 73 69 7a eof(tulips_)/siz
33e0: 65 6f 66 28 2a 74 75 6c 69 70 73 5f 29 29 3b 20 eof(*tulips_));
33f0: 0d 0a 09 69 6e 74 20 63 6f 73 74 73 5f 5b 5d 20 ...int costs_[]
3400: 3d 20 7b 20 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c = { 1,1,1,1,1,1,
3410: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3420: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3430: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3440: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3450: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3460: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3470: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3480: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3490: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
34a0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
34b0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
34c0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
34d0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
34e0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
34f0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3500: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3510: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3520: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3530: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3540: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3550: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3560: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3570: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3580: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3590: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
35a0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
35b0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
35c0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
35d0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
35e0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
35f0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3600: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3610: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3620: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3630: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3640: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
3650: 31 2c 31 2c 31 2c 31 2c 31 2c 31 20 7d 3b 0d 0a 1,1,1,1,1,1 };..
3660: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
3670: 63 6f 73 74 73 28 63 6f 73 74 73 5f 2c 20 63 6f costs(costs_, co
3680: 73 74 73 5f 2b 73 69 7a 65 6f 66 28 63 6f 73 74 sts_+sizeof(cost
3690: 73 5f 29 2f 73 69 7a 65 6f 66 28 2a 63 6f 73 74 s_)/sizeof(*cost
36a0: 73 5f 29 29 3b 20 0d 0a 09 64 6f 75 62 6c 65 20 s_)); ...double
36b0: 5f 20 3d 20 2d 32 3b 20 0d 0a 45 4e 44 0d 0a 2a _ = -2; ..END..*
36c0: 2f 0d 0a 7d 0d 0a 2f 2f 20 45 4e 44 20 43 55 54 /..}..// END CUT
36d0: 20 48 45 52 45 0d 0a HERE..