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 75 73 69 6e 67 <cstring>..using
0150: 20 6e 61 6d 65 73 70 61 63 65 20 73 74 64 3b 0d namespace std;.
0160: 0a 74 79 70 65 64 65 66 20 6c 6f 6e 67 20 6c 6f .typedef long lo
0170: 6e 67 20 4c 4c 3b 0d 0a 74 79 70 65 64 65 66 20 ng LL;..typedef
0180: 63 6f 6d 70 6c 65 78 3c 64 6f 75 62 6c 65 3e 20 complex<double>
0190: 43 4d 50 3b 0d 0a 0d 0a 74 65 6d 70 6c 61 74 65 CMP;....template
01a0: 3c 74 79 70 65 6e 61 6d 65 20 54 3e 0d 0a 73 74 <typename T>..st
01b0: 72 75 63 74 20 44 50 32 0d 0a 7b 0d 0a 09 63 6f ruct DP2..{...co
01c0: 6e 73 74 20 69 6e 74 20 4e 31 2c 20 4e 32 3b 0d nst int N1, N2;.
01d0: 0a 09 76 65 63 74 6f 72 3c 54 3e 20 64 61 74 61 ..vector<T> data
01e0: 3b 0d 0a 09 44 50 32 28 69 6e 74 20 4e 31 2c 20 ;...DP2(int N1,
01f0: 69 6e 74 20 4e 32 2c 20 63 6f 6e 73 74 20 54 26 int N2, const T&
0200: 20 74 20 3d 20 54 28 29 29 0d 0a 09 09 3a 20 4e t = T())....: N
0210: 31 28 4e 31 29 2c 20 4e 32 28 4e 32 29 2c 20 64 1(N1), N2(N2), d
0220: 61 74 61 28 4e 31 2a 4e 32 2c 20 74 29 20 7b 20 ata(N1*N2, t) {
0230: 61 73 73 65 72 74 28 64 61 74 61 2e 73 69 7a 65 assert(data.size
0240: 28 29 2a 73 69 7a 65 6f 66 28 54 29 3c 28 31 3c ()*sizeof(T)<(1<
0250: 3c 32 36 29 29 3b 20 7d 0d 0a 09 54 26 20 6f 70 <26)); }...T& op
0260: 65 72 61 74 6f 72 28 29 28 69 6e 74 20 69 31 2c erator()(int i1,
0270: 20 69 6e 74 20 69 32 29 0d 0a 09 09 7b 20 72 65 int i2)....{ re
0280: 74 75 72 6e 20 64 61 74 61 5b 20 28 69 31 2a 4e turn data[ (i1*N
0290: 32 29 2b 69 32 20 5d 3b 20 7d 0d 0a 7d 3b 0d 0a 2)+i2 ]; }..};..
02a0: 0d 0a 63 6c 61 73 73 20 4b 69 6e 67 64 6f 6d 58 ..class KingdomX
02b0: 45 6d 65 72 67 65 6e 63 79 53 74 61 69 72 63 61 EmergencyStairca
02c0: 73 65 20 7b 20 70 75 62 6c 69 63 3a 0d 0a 09 6c se { public:...l
02d0: 6f 6e 67 20 6c 6f 6e 67 20 64 65 74 65 72 6d 69 ong long determi
02e0: 6e 65 43 6f 73 74 28 73 74 72 69 6e 67 20 6c 65 neCost(string le
02f0: 66 74 42 75 69 6c 64 69 6e 67 2c 20 73 74 72 69 ftBuilding, stri
0300: 6e 67 20 72 69 67 68 74 42 75 69 6c 64 69 6e 67 ng rightBuilding
0310: 2c 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 63 , vector <int> c
0320: 6f 73 74 29 20 0d 0a 09 7b 0d 0a 09 09 63 6f 6e ost) ...{....con
0330: 73 74 20 4c 4c 20 6f 6f 20 3d 20 31 4c 4c 3c 3c st LL oo = 1LL<<
0340: 35 30 3b 0d 0a 09 09 63 6f 6e 73 74 20 69 6e 74 50;....const int
0350: 20 57 20 3d 20 63 6f 73 74 2e 73 69 7a 65 28 29 W = cost.size()
0360: 3b 0d 0a 09 09 63 6f 6e 73 74 20 69 6e 74 20 4c ;....const int L
0370: 20 3d 20 6c 65 66 74 42 75 69 6c 64 69 6e 67 2e = leftBuilding.
0380: 66 69 6e 64 5f 6c 61 73 74 5f 6f 66 28 27 59 27 find_last_of('Y'
0390: 29 2b 31 3b 0d 0a 09 09 63 6f 6e 73 74 20 69 6e )+1;....const in
03a0: 74 20 52 20 3d 20 72 69 67 68 74 42 75 69 6c 64 t R = rightBuild
03b0: 69 6e 67 2e 66 69 6e 64 5f 6c 61 73 74 5f 6f 66 ing.find_last_of
03c0: 28 27 59 27 29 2b 31 3b 0d 0a 09 09 63 6f 6e 73 ('Y')+1;....cons
03d0: 74 20 69 6e 74 20 48 20 3d 20 32 2a 6d 61 78 28 t int H = 2*max(
03e0: 4c 2c 52 29 2b 57 3b 0d 0a 0d 0a 09 09 4c 4c 20 L,R)+W;......LL
03f0: 62 65 73 74 20 3d 20 6f 6f 3b 0d 0a 09 09 44 50 best = oo;....DP
0400: 32 3c 4c 4c 3e 20 64 70 28 48 2b 31 2c 20 48 2b 2<LL> dp(H+1, H+
0410: 31 2c 20 6f 6f 29 3b 0d 0a 09 09 66 6f 72 28 69 1, oo);....for(i
0420: 6e 74 20 6c 3d 30 3b 20 6c 3c 3d 48 3b 20 6c 2b nt l=0; l<=H; l+
0430: 3d 32 29 0d 0a 09 09 66 6f 72 28 69 6e 74 20 72 =2)....for(int r
0440: 3d 30 3b 20 72 3c 3d 48 3b 20 72 2b 3d 32 29 0d =0; r<=H; r+=2).
0450: 0a 09 09 09 69 66 28 20 61 62 73 28 6c 2d 72 29 ....if( abs(l-r)
0460: 3c 3d 57 20 26 26 20 57 3c 3d 6c 2b 72 20 29 0d <=W && W<=l+r ).
0470: 0a 09 09 09 7b 0d 0a 09 09 09 09 69 66 28 20 6c ....{......if( l
0480: 3d 3d 30 20 29 0d 0a 09 09 09 09 7b 0d 0a 09 09 ==0 )......{....
0490: 09 09 09 4c 4c 20 63 6f 76 65 72 5f 63 6f 73 74 ...LL cover_cost
04a0: 20 3d 20 30 3b 0d 0a 09 09 09 09 09 66 6f 72 28 = 0;.......for(
04b0: 69 6e 74 20 72 72 3d 72 2d 32 3b 20 72 72 3e 3d int rr=r-2; rr>=
04c0: 30 3b 20 72 72 2d 3d 32 29 0d 0a 09 09 09 09 09 0; rr-=2).......
04d0: 09 69 66 28 20 72 69 67 68 74 42 75 69 6c 64 69 .if( rightBuildi
04e0: 6e 67 5b 72 72 2f 32 2d 31 5d 20 3d 3d 20 27 59 ng[rr/2-1] == 'Y
04f0: 27 20 29 0d 0a 09 09 09 09 09 09 09 63 6f 76 65 ' ).........cove
0500: 72 5f 63 6f 73 74 20 2b 3d 20 63 6f 73 74 5b 28 r_cost += cost[(
0510: 72 2d 72 72 29 2f 32 2d 31 5d 3b 0d 0a 09 09 09 r-rr)/2-1];.....
0520: 09 09 64 70 28 6c 2c 72 29 20 3d 20 63 6f 73 74 ..dp(l,r) = cost
0530: 5b 57 2d 31 5d 20 2b 20 63 6f 76 65 72 5f 63 6f [W-1] + cover_co
0540: 73 74 3b 0d 0a 09 09 09 09 7d 0d 0a 09 09 09 09 st;......}......
0550: 65 6c 73 65 20 69 66 28 20 72 3d 3d 30 20 29 0d else if( r==0 ).
0560: 0a 09 09 09 09 7b 0d 0a 09 09 09 09 09 4c 4c 20 .....{.......LL
0570: 63 6f 76 65 72 5f 63 6f 73 74 20 3d 20 30 3b 0d cover_cost = 0;.
0580: 0a 09 09 09 09 09 66 6f 72 28 69 6e 74 20 6c 6c ......for(int ll
0590: 3d 6c 2d 32 3b 20 6c 6c 3e 3d 30 3b 20 6c 6c 2d =l-2; ll>=0; ll-
05a0: 3d 32 29 0d 0a 09 09 09 09 09 09 69 66 28 20 6c =2)........if( l
05b0: 65 66 74 42 75 69 6c 64 69 6e 67 5b 6c 6c 2f 32 eftBuilding[ll/2
05c0: 2d 31 5d 20 3d 3d 20 27 59 27 20 29 0d 0a 09 09 -1] == 'Y' )....
05d0: 09 09 09 09 09 63 6f 76 65 72 5f 63 6f 73 74 20 .....cover_cost
05e0: 2b 3d 20 63 6f 73 74 5b 28 6c 2d 6c 6c 29 2f 32 += cost[(l-ll)/2
05f0: 2d 31 5d 3b 0d 0a 09 09 09 09 09 64 70 28 6c 2c -1];.......dp(l,
0600: 72 29 20 3d 20 63 6f 73 74 5b 57 2d 31 5d 20 2b r) = cost[W-1] +
0610: 20 63 6f 76 65 72 5f 63 6f 73 74 3b 0d 0a 09 09 cover_cost;....
0620: 09 09 7d 0d 0a 09 09 09 09 65 6c 73 65 0d 0a 09 ..}......else...
0630: 09 09 09 7b 0d 0a 09 09 09 09 09 63 6f 6e 73 74 ...{.......const
0640: 20 69 6e 74 20 6d 69 64 20 3d 20 57 2f 32 20 2d int mid = W/2 -
0650: 20 28 72 2d 6c 29 2f 32 3b 0d 0a 0d 0a 09 09 09 (r-l)/2;.......
0660: 09 09 4c 4c 20 63 75 72 5f 62 65 73 74 20 3d 20 ..LL cur_best =
0670: 6f 6f 3b 0d 0a 09 09 09 09 09 4c 4c 20 63 6f 76 oo;.......LL cov
0680: 65 72 5f 63 6f 73 74 20 3d 20 30 3b 0d 0a 09 09 er_cost = 0;....
0690: 09 09 09 66 6f 72 28 69 6e 74 20 6c 6c 3d 6c 2d ...for(int ll=l-
06a0: 32 3b 20 6c 6c 3e 3d 30 20 26 26 20 6c 6c 3e 3d 2; ll>=0 && ll>=
06b0: 72 2d 57 3b 20 6c 6c 2d 3d 32 29 0d 0a 09 09 09 r-W; ll-=2).....
06c0: 09 09 7b 0d 0a 09 09 09 09 09 09 69 66 28 20 6c ..{........if( l
06d0: 6c 2b 32 20 21 3d 20 6c 20 26 26 20 6c 65 66 74 l+2 != l && left
06e0: 42 75 69 6c 64 69 6e 67 5b 28 6c 6c 2b 32 29 2f Building[(ll+2)/
06f0: 32 2d 31 5d 3d 3d 27 59 27 20 29 0d 0a 09 09 09 2-1]=='Y' ).....
0700: 09 09 09 09 63 6f 76 65 72 5f 63 6f 73 74 20 2b ....cover_cost +
0710: 3d 20 63 6f 73 74 5b 28 6c 2d 6c 6c 2d 32 29 2f = cost[(l-ll-2)/
0720: 32 20 2d 20 31 5d 3b 0d 0a 09 09 09 09 09 09 63 2 - 1];........c
0730: 75 72 5f 62 65 73 74 20 3d 20 6d 69 6e 28 63 75 ur_best = min(cu
0740: 72 5f 62 65 73 74 2c 20 64 70 28 6c 6c 2c 72 29 r_best, dp(ll,r)
0750: 2b 63 6f 73 74 5b 6d 69 64 2d 31 5d 2b 63 6f 76 +cost[mid-1]+cov
0760: 65 72 5f 63 6f 73 74 29 3b 0d 0a 09 09 09 09 09 er_cost);.......
0770: 7d 0d 0a 09 09 09 09 09 63 6f 76 65 72 5f 63 6f }.......cover_co
0780: 73 74 20 3d 20 30 3b 0d 0a 09 09 09 09 09 66 6f st = 0;.......fo
0790: 72 28 69 6e 74 20 72 72 3d 72 2d 32 3b 20 72 72 r(int rr=r-2; rr
07a0: 3e 3d 30 20 26 26 20 72 72 3e 3d 6c 2d 57 3b 20 >=0 && rr>=l-W;
07b0: 72 72 2d 3d 32 29 0d 0a 09 09 09 09 09 7b 0d 0a rr-=2).......{..
07c0: 09 09 09 09 09 09 69 66 28 20 72 72 2b 32 20 21 ......if( rr+2 !
07d0: 3d 20 72 20 26 26 20 72 69 67 68 74 42 75 69 6c = r && rightBuil
07e0: 64 69 6e 67 5b 28 72 72 2b 32 29 2f 32 2d 31 5d ding[(rr+2)/2-1]
07f0: 3d 3d 27 59 27 20 29 0d 0a 09 09 09 09 09 09 09 =='Y' ).........
0800: 63 6f 76 65 72 5f 63 6f 73 74 20 2b 3d 20 63 6f cover_cost += co
0810: 73 74 5b 28 72 2d 72 72 2d 32 29 2f 32 20 2d 20 st[(r-rr-2)/2 -
0820: 31 5d 3b 0d 0a 09 09 09 09 09 09 63 75 72 5f 62 1];........cur_b
0830: 65 73 74 20 3d 20 6d 69 6e 28 63 75 72 5f 62 65 est = min(cur_be
0840: 73 74 2c 20 64 70 28 6c 2c 72 72 29 2b 63 6f 73 st, dp(l,rr)+cos
0850: 74 5b 57 2d 6d 69 64 2d 31 5d 2b 63 6f 76 65 72 t[W-mid-1]+cover
0860: 5f 63 6f 73 74 29 3b 0d 0a 09 09 09 09 09 7d 0d _cost);.......}.
0870: 0a 09 09 09 09 09 64 70 28 6c 2c 72 29 20 3d 20 ......dp(l,r) =
0880: 63 75 72 5f 62 65 73 74 3b 0d 0a 09 09 09 09 7d cur_best;......}
0890: 0d 0a 09 09 09 09 69 66 28 20 32 2a 4c 3c 3d 6c ......if( 2*L<=l
08a0: 20 26 26 20 32 2a 52 3c 3d 72 20 29 0d 0a 09 09 && 2*R<=r )....
08b0: 09 09 09 62 65 73 74 20 3d 20 6d 69 6e 28 62 65 ...best = min(be
08c0: 73 74 2c 20 64 70 28 6c 2c 72 29 29 3b 0d 0a 09 st, dp(l,r));...
08d0: 09 09 7d 0d 0a 09 09 72 65 74 75 72 6e 20 62 65 ..}....return be
08e0: 73 74 3b 0d 0a 09 7d 0d 0a 7d 3b 0d 0a 0d 0a 2f st;...}..};..../
08f0: 2f 20 42 45 47 49 4e 20 43 55 54 20 48 45 52 45 / BEGIN CUT HERE
0900: 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 74 69 6d ..#include <ctim
0910: 65 3e 0d 0a 64 6f 75 62 6c 65 20 73 74 61 72 74 e>..double start
0920: 5f 74 69 6d 65 3b 20 73 74 72 69 6e 67 20 74 69 _time; string ti
0930: 6d 65 72 28 29 0d 0a 20 7b 20 6f 73 74 72 69 6e mer().. { ostrin
0940: 67 73 74 72 65 61 6d 20 6f 73 3b 20 6f 73 20 3c gstream os; os <
0950: 3c 20 22 20 28 22 20 3c 3c 20 69 6e 74 28 28 63 < " (" << int((c
0960: 6c 6f 63 6b 28 29 2d 73 74 61 72 74 5f 74 69 6d lock()-start_tim
0970: 65 29 2f 43 4c 4f 43 4b 53 5f 50 45 52 5f 53 45 e)/CLOCKS_PER_SE
0980: 43 2a 31 30 30 30 29 20 3c 3c 20 22 20 6d 73 65 C*1000) << " mse
0990: 63 29 22 3b 20 72 65 74 75 72 6e 20 6f 73 2e 73 c)"; return os.s
09a0: 74 72 28 29 3b 20 7d 0d 0a 74 65 6d 70 6c 61 74 tr(); }..templat
09b0: 65 3c 74 79 70 65 6e 61 6d 65 20 54 3e 20 6f 73 e<typename T> os
09c0: 74 72 65 61 6d 26 20 6f 70 65 72 61 74 6f 72 3c tream& operator<
09d0: 3c 28 6f 73 74 72 65 61 6d 26 20 6f 73 2c 20 63 <(ostream& os, c
09e0: 6f 6e 73 74 20 76 65 63 74 6f 72 3c 54 3e 26 20 onst vector<T>&
09f0: 76 29 0d 0a 20 7b 20 6f 73 20 3c 3c 20 22 7b 20 v).. { os << "{
0a00: 22 3b 0d 0a 20 20 20 66 6f 72 28 74 79 70 65 6e ";.. for(typen
0a10: 61 6d 65 20 76 65 63 74 6f 72 3c 54 3e 3a 3a 63 ame vector<T>::c
0a20: 6f 6e 73 74 5f 69 74 65 72 61 74 6f 72 20 69 74 onst_iterator it
0a30: 3d 76 2e 62 65 67 69 6e 28 29 3b 20 69 74 21 3d =v.begin(); it!=
0a40: 76 2e 65 6e 64 28 29 3b 20 2b 2b 69 74 29 0d 0a v.end(); ++it)..
0a50: 20 20 20 6f 73 20 3c 3c 20 27 5c 22 27 20 3c 3c os << '\"' <<
0a60: 20 2a 69 74 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 *it << '\"' <<
0a70: 28 69 74 2b 31 3d 3d 76 2e 65 6e 64 28 29 20 3f (it+1==v.end() ?
0a80: 20 22 22 20 3a 20 22 2c 20 22 29 3b 20 6f 73 20 "" : ", "); os
0a90: 3c 3c 20 22 20 7d 22 3b 20 72 65 74 75 72 6e 20 << " }"; return
0aa0: 6f 73 3b 20 7d 0d 0a 76 6f 69 64 20 76 65 72 69 os; }..void veri
0ab0: 66 79 5f 63 61 73 65 28 63 6f 6e 73 74 20 6c 6f fy_case(const lo
0ac0: 6e 67 20 6c 6f 6e 67 26 20 45 78 70 65 63 74 65 ng long& Expecte
0ad0: 64 2c 20 63 6f 6e 73 74 20 6c 6f 6e 67 20 6c 6f d, const long lo
0ae0: 6e 67 26 20 52 65 63 65 69 76 65 64 29 20 7b 0d ng& Received) {.
0af0: 0a 20 62 6f 6f 6c 20 6f 6b 20 3d 20 28 45 78 70 . bool ok = (Exp
0b00: 65 63 74 65 64 20 3d 3d 20 52 65 63 65 69 76 65 ected == Receive
0b10: 64 29 3b 0d 0a 20 69 66 28 6f 6b 29 20 63 65 72 d);.. if(ok) cer
0b20: 72 20 3c 3c 20 22 50 41 53 53 45 44 22 20 3c 3c r << "PASSED" <<
0b30: 20 74 69 6d 65 72 28 29 20 3c 3c 20 65 6e 64 6c timer() << endl
0b40: 3b 20 20 65 6c 73 65 20 7b 20 63 65 72 72 20 3c ; else { cerr <
0b50: 3c 20 22 46 41 49 4c 45 44 22 20 3c 3c 20 74 69 < "FAILED" << ti
0b60: 6d 65 72 28 29 20 3c 3c 20 65 6e 64 6c 3b 0d 0a mer() << endl;..
0b70: 20 63 65 72 72 20 3c 3c 20 22 5c 74 6f 3a 20 5c cerr << "\to: \
0b80: 22 22 20 3c 3c 20 45 78 70 65 63 74 65 64 20 3c "" << Expected <
0b90: 3c 20 27 5c 22 27 20 3c 3c 20 65 6e 64 6c 20 3c < '\"' << endl <
0ba0: 3c 20 22 5c 74 78 3a 20 5c 22 22 20 3c 3c 20 52 < "\tx: \"" << R
0bb0: 65 63 65 69 76 65 64 20 3c 3c 20 27 5c 22 27 20 eceived << '\"'
0bc0: 3c 3c 20 65 6e 64 6c 3b 20 7d 20 7d 0d 0a 23 64 << endl; } }..#d
0bd0: 65 66 69 6e 65 20 43 41 53 45 28 4e 29 20 7b 63 efine CASE(N) {c
0be0: 65 72 72 20 3c 3c 20 22 54 65 73 74 20 43 61 73 err << "Test Cas
0bf0: 65 20 23 22 20 3c 3c 20 4e 20 3c 3c 20 22 2e 2e e #" << N << "..
0c00: 2e 22 20 3c 3c 20 66 6c 75 73 68 3b 20 73 74 61 ." << flush; sta
0c10: 72 74 5f 74 69 6d 65 3d 63 6c 6f 63 6b 28 29 3b rt_time=clock();
0c20: 0d 0a 23 64 65 66 69 6e 65 20 45 4e 44 09 20 76 ..#define END. v
0c30: 65 72 69 66 79 5f 63 61 73 65 28 5f 2c 20 4b 69 erify_case(_, Ki
0c40: 6e 67 64 6f 6d 58 45 6d 65 72 67 65 6e 63 79 53 ngdomXEmergencyS
0c50: 74 61 69 72 63 61 73 65 28 29 2e 64 65 74 65 72 taircase().deter
0c60: 6d 69 6e 65 43 6f 73 74 28 6c 65 66 74 42 75 69 mineCost(leftBui
0c70: 6c 64 69 6e 67 2c 20 72 69 67 68 74 42 75 69 6c lding, rightBuil
0c80: 64 69 6e 67 2c 20 63 6f 73 74 29 29 3b 7d 0d 0a ding, cost));}..
0c90: 69 6e 74 20 6d 61 69 6e 28 29 7b 0d 0a 0d 0a 43 int main(){....C
0ca0: 41 53 45 28 30 29 0d 0a 09 73 74 72 69 6e 67 20 ASE(0)...string
0cb0: 6c 65 66 74 42 75 69 6c 64 69 6e 67 20 3d 20 22 leftBuilding = "
0cc0: 59 4e 59 59 22 3b 20 0d 0a 09 73 74 72 69 6e 67 YNYY"; ...string
0cd0: 20 72 69 67 68 74 42 75 69 6c 64 69 6e 67 20 3d rightBuilding =
0ce0: 20 22 4e 4e 4e 59 22 3b 20 0d 0a 09 69 6e 74 20 "NNNY"; ...int
0cf0: 63 6f 73 74 5f 5b 5d 20 3d 20 7b 31 30 2c 20 34 cost_[] = {10, 4
0d00: 30 2c 20 31 38 2c 20 32 35 7d 3b 0d 0a 09 20 20 0, 18, 25};...
0d10: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 63 6f 73 vector <int> cos
0d20: 74 28 63 6f 73 74 5f 2c 20 63 6f 73 74 5f 2b 73 t(cost_, cost_+s
0d30: 69 7a 65 6f 66 28 63 6f 73 74 5f 29 2f 73 69 7a izeof(cost_)/siz
0d40: 65 6f 66 28 2a 63 6f 73 74 5f 29 29 3b 20 0d 0a eof(*cost_)); ..
0d50: 09 6c 6f 6e 67 20 6c 6f 6e 67 20 5f 20 3d 20 39 .long long _ = 9
0d60: 38 4c 4c 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 8LL; ..END..CASE
0d70: 28 31 29 0d 0a 09 73 74 72 69 6e 67 20 6c 65 66 (1)...string lef
0d80: 74 42 75 69 6c 64 69 6e 67 20 3d 20 22 4e 22 3b tBuilding = "N";
0d90: 20 0d 0a 09 73 74 72 69 6e 67 20 72 69 67 68 74 ...string right
0da0: 42 75 69 6c 64 69 6e 67 20 3d 20 22 59 22 3b 20 Building = "Y";
0db0: 0d 0a 09 69 6e 74 20 63 6f 73 74 5f 5b 5d 20 3d ...int cost_[] =
0dc0: 20 7b 31 2c 20 31 30 30 30 7d 3b 0d 0a 09 20 20 {1, 1000};...
0dd0: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 63 6f 73 vector <int> cos
0de0: 74 28 63 6f 73 74 5f 2c 20 63 6f 73 74 5f 2b 73 t(cost_, cost_+s
0df0: 69 7a 65 6f 66 28 63 6f 73 74 5f 29 2f 73 69 7a izeof(cost_)/siz
0e00: 65 6f 66 28 2a 63 6f 73 74 5f 29 29 3b 20 0d 0a eof(*cost_)); ..
0e10: 09 6c 6f 6e 67 20 6c 6f 6e 67 20 5f 20 3d 20 31 .long long _ = 1
0e20: 30 30 30 4c 4c 3b 20 0d 0a 45 4e 44 0d 0a 43 41 000LL; ..END..CA
0e30: 53 45 28 32 29 0d 0a 09 73 74 72 69 6e 67 20 6c SE(2)...string l
0e40: 65 66 74 42 75 69 6c 64 69 6e 67 20 3d 20 22 4e eftBuilding = "N
0e50: 4e 4e 4e 4e 4e 4e 59 22 3b 20 0d 0a 09 73 74 72 NNNNNNY"; ...str
0e60: 69 6e 67 20 72 69 67 68 74 42 75 69 6c 64 69 6e ing rightBuildin
0e70: 67 20 3d 20 22 4e 4e 4e 4e 4e 4e 4e 59 22 3b 20 g = "NNNNNNNY";
0e80: 0d 0a 09 69 6e 74 20 63 6f 73 74 5f 5b 5d 20 3d ...int cost_[] =
0e90: 20 7b 31 2c 20 32 7d 3b 0d 0a 09 20 20 76 65 63 {1, 2};... vec
0ea0: 74 6f 72 20 3c 69 6e 74 3e 20 63 6f 73 74 28 63 tor <int> cost(c
0eb0: 6f 73 74 5f 2c 20 63 6f 73 74 5f 2b 73 69 7a 65 ost_, cost_+size
0ec0: 6f 66 28 63 6f 73 74 5f 29 2f 73 69 7a 65 6f 66 of(cost_)/sizeof
0ed0: 28 2a 63 6f 73 74 5f 29 29 3b 20 0d 0a 09 6c 6f (*cost_)); ...lo
0ee0: 6e 67 20 6c 6f 6e 67 20 5f 20 3d 20 31 37 4c 4c ng long _ = 17LL
0ef0: 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 33 29 ; ..END..CASE(3)
0f00: 0d 0a 09 73 74 72 69 6e 67 20 6c 65 66 74 42 75 ...string leftBu
0f10: 69 6c 64 69 6e 67 20 3d 20 22 4e 4e 4e 4e 4e 4e ilding = "NNNNNN
0f20: 4e 4e 4e 4e 4e 4e 4e 4e 4e 4e 4e 4e 4e 4e 4e 4e NNNNNNNNNNNNNNNN
0f30: 4e 4e 4e 4e 4e 4e 4e 4e 4e 4e 22 3b 20 0d 0a 09 NNNNNNNNNN"; ...
0f40: 73 74 72 69 6e 67 20 72 69 67 68 74 42 75 69 6c string rightBuil
0f50: 64 69 6e 67 20 3d 20 22 4e 4e 4e 4e 4e 4e 4e 4e ding = "NNNNNNNN
0f60: 4e 4e 4e 4e 4e 4e 4e 4e 4e 4e 4e 4e 4e 4e 4e 4e NNNNNNNNNNNNNNNN
0f70: 4e 4e 4e 4e 4e 4e 4e 59 22 3b 20 0d 0a 09 69 6e NNNNNNNY"; ...in
0f80: 74 20 63 6f 73 74 5f 5b 5d 20 3d 20 7b 38 30 30 t cost_[] = {800
0f90: 30 30 30 30 30 30 2c 38 30 30 30 30 30 30 30 30 000000,800000000
0fa0: 2c 38 30 30 30 30 30 30 30 30 2c 38 30 30 30 30 ,800000000,80000
0fb0: 30 30 30 30 2c 38 30 30 30 30 30 30 30 30 2c 38 0000,800000000,8
0fc0: 30 30 30 30 30 30 30 30 2c 38 30 30 30 30 30 30 00000000,8000000
0fd0: 30 30 2c 38 30 30 30 30 30 30 30 30 7d 3b 0d 0a 00,800000000};..
0fe0: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
0ff0: 63 6f 73 74 28 63 6f 73 74 5f 2c 20 63 6f 73 74 cost(cost_, cost
1000: 5f 2b 73 69 7a 65 6f 66 28 63 6f 73 74 5f 29 2f _+sizeof(cost_)/
1010: 73 69 7a 65 6f 66 28 2a 63 6f 73 74 5f 29 29 3b sizeof(*cost_));
1020: 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 5f 20 ...long long _
1030: 3d 20 36 34 30 30 30 30 30 30 30 30 4c 4c 3b 20 = 6400000000LL;
1040: 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 34 29 0d 0a ..END..CASE(4)..
1050: 09 73 74 72 69 6e 67 20 6c 65 66 74 42 75 69 6c .string leftBuil
1060: 64 69 6e 67 20 3d 20 22 4e 4e 59 22 3b 20 0d 0a ding = "NNY"; ..
1070: 09 73 74 72 69 6e 67 20 72 69 67 68 74 42 75 69 .string rightBui
1080: 6c 64 69 6e 67 20 3d 20 22 4e 4e 59 59 59 22 3b lding = "NNYYY";
1090: 20 0d 0a 09 69 6e 74 20 63 6f 73 74 5f 5b 5d 20 ...int cost_[]
10a0: 3d 20 7b 31 30 30 30 30 2c 20 31 30 2c 20 34 30 = {10000, 10, 40
10b0: 2c 20 31 30 30 30 30 2c 20 38 30 2c 20 38 30 7d , 10000, 80, 80}
10c0: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e ;... vector <in
10d0: 74 3e 20 63 6f 73 74 28 63 6f 73 74 5f 2c 20 63 t> cost(cost_, c
10e0: 6f 73 74 5f 2b 73 69 7a 65 6f 66 28 63 6f 73 74 ost_+sizeof(cost
10f0: 5f 29 2f 73 69 7a 65 6f 66 28 2a 63 6f 73 74 5f _)/sizeof(*cost_
1100: 29 29 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 )); ...long long
1110: 20 5f 20 3d 20 32 32 30 4c 4c 3b 20 0d 0a 45 4e _ = 220LL; ..EN
1120: 44 0d 0a 43 41 53 45 28 35 29 0d 0a 73 74 72 69 D..CASE(5)..stri
1130: 6e 67 20 6c 65 66 74 42 75 69 6c 64 69 6e 67 20 ng leftBuilding
1140: 3d 20 22 59 4e 59 4e 59 59 4e 59 4e 59 59 4e 59 = "YNYNYYNYNYYNY
1150: 4e 59 59 4e 59 4e 59 59 4e 59 4e 59 59 4e 59 4e NYYNYNYYNYNYYNYN
1160: 59 59 4e 59 4e 59 59 4e 59 4e 59 59 4e 59 4e 59 YYNYNYYNYNYYNYNY
1170: 59 4e 59 4e 59 22 3b 0d 0a 73 74 72 69 6e 67 20 YNYNY";..string
1180: 72 69 67 68 74 42 75 69 6c 64 69 6e 67 20 3d 20 rightBuilding =
1190: 22 59 4e 59 4e 59 59 4e 59 4e 59 59 4e 59 4e 59 "YNYNYYNYNYYNYNY
11a0: 59 4e 59 4e 59 59 4e 59 4e 59 59 4e 59 4e 59 59 YNYNYYNYNYYNYNYY
11b0: 4e 59 4e 59 59 4e 59 4e 59 59 4e 59 4e 59 59 4e NYNYYNYNYYNYNYYN
11c0: 59 4e 59 22 3b 20 0d 0a 09 69 6e 74 20 63 6f 73 YNY"; ...int cos
11d0: 74 5f 5b 5d 20 3d 20 7b 39 35 38 32 33 31 31 31 t_[] = {95823111
11e0: 33 2c 20 39 35 39 39 33 39 39 33 39 2c 20 39 39 3, 959939939, 99
11f0: 39 39 39 39 39 39 39 2c 20 39 35 34 33 32 31 33 9999999, 9543213
1200: 32 31 2c 20 31 30 30 30 30 30 30 30 30 30 2c 20 21, 1000000000,
1210: 39 39 38 39 39 38 39 39 38 2c 20 39 38 37 39 38 998998998, 98798
1220: 37 39 38 37 2c 20 39 39 39 38 38 38 37 37 37 2c 7987, 999888777,
1230: 20 31 30 30 30 30 30 30 30 30 30 2c 20 31 30 30 1000000000, 100
1240: 30 30 30 30 30 30 30 7d 3b 0d 0a 09 20 20 76 65 0000000};... ve
1250: 63 74 6f 72 20 3c 69 6e 74 3e 20 63 6f 73 74 28 ctor <int> cost(
1260: 63 6f 73 74 5f 2c 20 63 6f 73 74 5f 2b 73 69 7a cost_, cost_+siz
1270: 65 6f 66 28 63 6f 73 74 5f 29 2f 73 69 7a 65 6f eof(cost_)/sizeo
1280: 66 28 2a 63 6f 73 74 5f 29 29 3b 20 0d 0a 09 6c f(*cost_)); ...l
1290: 6f 6e 67 20 6c 6f 6e 67 20 5f 20 3d 20 35 38 32 ong long _ = 582
12a0: 31 32 33 30 35 32 31 31 4c 4c 3b 20 0d 0a 45 4e 12305211LL; ..EN
12b0: 44 0d 0a 2f 2a 0d 0a 43 41 53 45 28 36 29 0d 0a D../*..CASE(6)..
12c0: 09 73 74 72 69 6e 67 20 6c 65 66 74 42 75 69 6c .string leftBuil
12d0: 64 69 6e 67 20 3d 20 3b 20 0d 0a 09 73 74 72 69 ding = ; ...stri
12e0: 6e 67 20 72 69 67 68 74 42 75 69 6c 64 69 6e 67 ng rightBuilding
12f0: 20 3d 20 3b 20 0d 0a 09 69 6e 74 20 63 6f 73 74 = ; ...int cost
1300: 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 63 74 _[] = ;... vect
1310: 6f 72 20 3c 69 6e 74 3e 20 63 6f 73 74 28 63 6f or <int> cost(co
1320: 73 74 5f 2c 20 63 6f 73 74 5f 2b 73 69 7a 65 6f st_, cost_+sizeo
1330: 66 28 63 6f 73 74 5f 29 2f 73 69 7a 65 6f 66 28 f(cost_)/sizeof(
1340: 2a 63 6f 73 74 5f 29 29 3b 20 0d 0a 09 6c 6f 6e *cost_)); ...lon
1350: 67 20 6c 6f 6e 67 20 5f 20 3d 20 4c 4c 3b 20 0d g long _ = LL; .
1360: 0a 45 4e 44 0d 0a 2a 2f 0d 0a 7d 0d 0a 2f 2f 20 .END..*/..}..//
1370: 45 4e 44 20 43 55 54 20 48 45 52 45 0d 0a END CUT HERE..