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 75 73 69 6e 67 20 6e 61 6d sert>..using nam
0140: 65 73 70 61 63 65 20 73 74 64 3b 0d 0a 74 79 70 espace std;..typ
0150: 65 64 65 66 20 6c 6f 6e 67 20 6c 6f 6e 67 20 4c edef long long L
0160: 4c 3b 0d 0a 74 79 70 65 64 65 66 20 6c 6f 6e 67 L;..typedef long
0170: 20 64 6f 75 62 6c 65 20 4c 44 3b 0d 0a 74 79 70 double LD;..typ
0180: 65 64 65 66 20 63 6f 6d 70 6c 65 78 3c 4c 44 3e edef complex<LD>
0190: 20 43 4d 50 3b 0d 0a 0d 0a 63 6c 61 73 73 20 54 CMP;....class T
01a0: 68 65 4d 6f 75 6e 74 61 69 6e 20 7b 20 70 75 62 heMountain { pub
01b0: 6c 69 63 3a 0d 0a 09 69 6e 74 20 6d 69 6e 53 75 lic:...int minSu
01c0: 6d 28 69 6e 74 20 48 2c 20 69 6e 74 20 57 2c 20 m(int H, int W,
01d0: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 59 2c 20 vector <int> Y,
01e0: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 58 2c 20 vector <int> X,
01f0: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 56 29 0d vector <int> V).
0200: 0a 09 7b 0d 0a 09 09 63 6f 6e 73 74 20 69 6e 74 ..{....const int
0210: 20 4e 20 3d 20 59 2e 73 69 7a 65 28 29 3b 0d 0a N = Y.size();..
0220: 09 09 73 74 61 74 69 63 20 63 6f 6e 73 74 20 69 ..static const i
0230: 6e 74 20 49 4e 46 20 3d 20 30 78 33 66 66 66 66 nt INF = 0x3ffff
0240: 66 66 66 3b 0d 0a 09 09 69 6e 74 20 62 65 73 74 fff;....int best
0250: 20 3d 20 49 4e 46 3b 0d 0a 0d 0a 09 09 76 65 63 = INF;......vec
0260: 74 6f 72 3c 20 76 65 63 74 6f 72 3c 69 6e 74 3e tor< vector<int>
0270: 20 3e 20 66 69 78 65 64 28 48 2c 20 76 65 63 74 > fixed(H, vect
0280: 6f 72 3c 69 6e 74 3e 28 57 2c 20 30 29 29 3b 0d or<int>(W, 0));.
0290: 0a 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 ...for(int i=0;
02a0: 69 3c 4e 3b 20 2b 2b 69 29 0d 0a 09 09 09 66 69 i<N; ++i).....fi
02b0: 78 65 64 5b 59 5b 69 5d 5d 5b 58 5b 69 5d 5d 20 xed[Y[i]][X[i]]
02c0: 3d 20 56 5b 69 5d 3b 0d 0a 0d 0a 09 09 66 6f 72 = V[i];......for
02d0: 28 69 6e 74 20 78 3d 30 3b 20 78 3c 57 3b 20 2b (int x=0; x<W; +
02e0: 2b 78 29 0d 0a 09 09 7b 0d 0a 09 09 09 76 65 63 +x)....{.....vec
02f0: 74 6f 72 3c 20 76 65 63 74 6f 72 3c 69 6e 74 3e tor< vector<int>
0300: 20 3e 20 74 64 28 48 2c 20 76 65 63 74 6f 72 3c > td(H, vector<
0310: 69 6e 74 3e 28 57 29 29 3b 0d 0a 09 09 09 76 65 int>(W));.....ve
0320: 63 74 6f 72 3c 69 6e 74 3e 20 74 64 5f 73 75 6d ctor<int> td_sum
0330: 28 48 29 3b 0d 0a 09 09 09 69 6e 74 20 74 64 5f (H);.....int td_
0340: 65 6e 64 20 3d 20 30 3b 0d 0a 09 09 09 66 6f 72 end = 0;.....for
0350: 28 69 6e 74 20 79 3d 30 3b 20 79 3c 48 3b 20 2b (int y=0; y<H; +
0360: 2b 79 29 0d 0a 09 09 09 7b 0d 0a 09 09 09 09 66 +y).....{......f
0370: 6f 72 28 69 6e 74 20 61 3d 30 3b 20 61 3c 78 3b or(int a=0; a<x;
0380: 20 2b 2b 61 29 20 7b 0d 0a 09 09 09 09 09 69 6e ++a) {.......in
0390: 74 20 72 65 71 20 3d 20 31 3b 0d 0a 09 09 09 09 t req = 1;......
03a0: 09 69 66 28 30 3c 3d 61 2d 31 26 26 61 2d 31 3c .if(0<=a-1&&a-1<
03b0: 57 29 20 72 65 71 20 3d 20 6d 61 78 28 72 65 71 W) req = max(req
03c0: 2c 20 74 64 5b 79 5d 5b 61 2d 31 5d 2b 31 29 3b , td[y][a-1]+1);
03d0: 0d 0a 09 09 09 09 09 69 66 28 30 3c 3d 79 2d 31 .......if(0<=y-1
03e0: 26 26 79 2d 31 3c 48 29 20 72 65 71 20 3d 20 6d &&y-1<H) req = m
03f0: 61 78 28 72 65 71 2c 20 74 64 5b 79 2d 31 5d 5b ax(req, td[y-1][
0400: 61 5d 2b 31 29 3b 0d 0a 09 09 09 09 09 69 66 28 a]+1);.......if(
0410: 66 69 78 65 64 5b 79 5d 5b 61 5d 29 20 7b 0d 0a fixed[y][a]) {..
0420: 09 09 09 09 09 09 69 66 28 66 69 78 65 64 5b 79 ......if(fixed[y
0430: 5d 5b 61 5d 20 3c 20 72 65 71 29 0d 0a 09 09 09 ][a] < req).....
0440: 09 09 09 09 67 6f 74 6f 20 6c 61 62 65 6c 5f 74 ....goto label_t
0450: 64 5f 65 6e 64 3b 0d 0a 09 09 09 09 09 09 74 64 d_end;........td
0460: 5b 79 5d 5b 61 5d 20 3d 20 66 69 78 65 64 5b 79 [y][a] = fixed[y
0470: 5d 5b 61 5d 3b 0d 0a 09 09 09 09 09 7d 20 65 6c ][a];.......} el
0480: 73 65 20 7b 0d 0a 09 09 09 09 09 09 74 64 5b 79 se {........td[y
0490: 5d 5b 61 5d 20 3d 20 72 65 71 3b 0d 0a 09 09 09 ][a] = req;.....
04a0: 09 09 7d 0d 0a 09 09 09 09 7d 0d 0a 09 09 09 09 ..}......}......
04b0: 66 6f 72 28 69 6e 74 20 61 3d 57 2d 31 3b 20 61 for(int a=W-1; a
04c0: 3e 78 3b 20 2d 2d 61 29 20 7b 0d 0a 09 09 09 09 >x; --a) {......
04d0: 09 69 6e 74 20 72 65 71 20 3d 20 31 3b 0d 0a 09 .int req = 1;...
04e0: 09 09 09 09 69 66 28 30 3c 3d 61 2b 31 26 26 61 ....if(0<=a+1&&a
04f0: 2b 31 3c 57 29 20 72 65 71 20 3d 20 6d 61 78 28 +1<W) req = max(
0500: 72 65 71 2c 20 74 64 5b 79 5d 5b 61 2b 31 5d 2b req, td[y][a+1]+
0510: 31 29 3b 0d 0a 09 09 09 09 09 69 66 28 30 3c 3d 1);.......if(0<=
0520: 79 2d 31 26 26 79 2d 31 3c 48 29 20 72 65 71 20 y-1&&y-1<H) req
0530: 3d 20 6d 61 78 28 72 65 71 2c 20 74 64 5b 79 2d = max(req, td[y-
0540: 31 5d 5b 61 5d 2b 31 29 3b 0d 0a 09 09 09 09 09 1][a]+1);.......
0550: 69 66 28 66 69 78 65 64 5b 79 5d 5b 61 5d 29 20 if(fixed[y][a])
0560: 7b 0d 0a 09 09 09 09 09 09 69 66 28 66 69 78 65 {........if(fixe
0570: 64 5b 79 5d 5b 61 5d 20 3c 20 72 65 71 29 0d 0a d[y][a] < req)..
0580: 09 09 09 09 09 09 09 67 6f 74 6f 20 6c 61 62 65 .......goto labe
0590: 6c 5f 74 64 5f 65 6e 64 3b 0d 0a 09 09 09 09 09 l_td_end;.......
05a0: 09 74 64 5b 79 5d 5b 61 5d 20 3d 20 66 69 78 65 .td[y][a] = fixe
05b0: 64 5b 79 5d 5b 61 5d 3b 0d 0a 09 09 09 09 09 7d d[y][a];.......}
05c0: 20 65 6c 73 65 20 7b 0d 0a 09 09 09 09 09 09 74 else {........t
05d0: 64 5b 79 5d 5b 61 5d 20 3d 20 72 65 71 3b 0d 0a d[y][a] = req;..
05e0: 09 09 09 09 09 7d 0d 0a 09 09 09 09 7d 0d 0a 09 .....}......}...
05f0: 09 09 09 69 6e 74 20 61 20 3d 20 78 3b 0d 0a 09 ...int a = x;...
0600: 09 09 09 7b 0d 0a 09 09 09 09 09 69 6e 74 20 72 ...{.......int r
0610: 65 71 20 3d 20 31 3b 0d 0a 09 09 09 09 09 69 66 eq = 1;.......if
0620: 28 30 3c 3d 61 2d 31 26 26 61 2d 31 3c 57 29 20 (0<=a-1&&a-1<W)
0630: 72 65 71 20 3d 20 6d 61 78 28 72 65 71 2c 20 74 req = max(req, t
0640: 64 5b 79 5d 5b 61 2d 31 5d 2b 31 29 3b 0d 0a 09 d[y][a-1]+1);...
0650: 09 09 09 09 69 66 28 30 3c 3d 61 2b 31 26 26 61 ....if(0<=a+1&&a
0660: 2b 31 3c 57 29 20 72 65 71 20 3d 20 6d 61 78 28 +1<W) req = max(
0670: 72 65 71 2c 20 74 64 5b 79 5d 5b 61 2b 31 5d 2b req, td[y][a+1]+
0680: 31 29 3b 0d 0a 09 09 09 09 09 69 66 28 30 3c 3d 1);.......if(0<=
0690: 79 2d 31 26 26 79 2d 31 3c 48 29 20 72 65 71 20 y-1&&y-1<H) req
06a0: 3d 20 6d 61 78 28 72 65 71 2c 20 74 64 5b 79 2d = max(req, td[y-
06b0: 31 5d 5b 61 5d 2b 31 29 3b 0d 0a 09 09 09 09 09 1][a]+1);.......
06c0: 69 66 28 66 69 78 65 64 5b 79 5d 5b 61 5d 29 20 if(fixed[y][a])
06d0: 7b 0d 0a 09 09 09 09 09 09 69 66 28 66 69 78 65 {........if(fixe
06e0: 64 5b 79 5d 5b 61 5d 20 3c 20 72 65 71 29 0d 0a d[y][a] < req)..
06f0: 09 09 09 09 09 09 09 67 6f 74 6f 20 6c 61 62 65 .......goto labe
0700: 6c 5f 74 64 5f 65 6e 64 3b 0d 0a 09 09 09 09 09 l_td_end;.......
0710: 09 74 64 5b 79 5d 5b 61 5d 20 3d 20 66 69 78 65 .td[y][a] = fixe
0720: 64 5b 79 5d 5b 61 5d 3b 0d 0a 09 09 09 09 09 7d d[y][a];.......}
0730: 20 65 6c 73 65 20 7b 0d 0a 09 09 09 09 09 09 74 else {........t
0740: 64 5b 79 5d 5b 61 5d 20 3d 20 72 65 71 3b 0d 0a d[y][a] = req;..
0750: 09 09 09 09 09 7d 0d 0a 09 09 09 09 7d 0d 0a 09 .....}......}...
0760: 09 09 09 74 64 5f 73 75 6d 5b 79 5d 20 3d 20 61 ...td_sum[y] = a
0770: 63 63 75 6d 75 6c 61 74 65 28 74 64 5b 79 5d 2e ccumulate(td[y].
0780: 62 65 67 69 6e 28 29 2c 20 74 64 5b 79 5d 2e 65 begin(), td[y].e
0790: 6e 64 28 29 2c 20 30 29 3b 0d 0a 09 09 09 09 74 nd(), 0);......t
07a0: 64 5f 65 6e 64 20 2b 2b 3b 0d 0a 09 09 09 7d 0d d_end ++;.....}.
07b0: 0a 09 09 6c 61 62 65 6c 5f 74 64 5f 65 6e 64 3a ...label_td_end:
07c0: 3b 0d 0a 0d 0a 09 09 09 76 65 63 74 6f 72 3c 20 ;.......vector<
07d0: 76 65 63 74 6f 72 3c 69 6e 74 3e 20 3e 20 62 75 vector<int> > bu
07e0: 28 48 2c 20 76 65 63 74 6f 72 3c 69 6e 74 3e 28 (H, vector<int>(
07f0: 57 29 29 3b 0d 0a 09 09 09 76 65 63 74 6f 72 3c W));.....vector<
0800: 69 6e 74 3e 20 62 75 5f 73 75 6d 28 48 29 3b 0d int> bu_sum(H);.
0810: 0a 09 09 09 69 6e 74 20 62 75 5f 62 65 67 69 6e ....int bu_begin
0820: 20 3d 20 48 3b 0d 0a 09 09 09 66 6f 72 28 69 6e = H;.....for(in
0830: 74 20 79 3d 48 2d 31 3b 20 79 3e 3d 30 3b 20 2d t y=H-1; y>=0; -
0840: 2d 79 29 0d 0a 09 09 09 7b 0d 0a 09 09 09 09 66 -y).....{......f
0850: 6f 72 28 69 6e 74 20 61 3d 30 3b 20 61 3c 78 3b or(int a=0; a<x;
0860: 20 2b 2b 61 29 20 7b 0d 0a 09 09 09 09 09 69 6e ++a) {.......in
0870: 74 20 72 65 71 20 3d 20 31 3b 0d 0a 09 09 09 09 t req = 1;......
0880: 09 69 66 28 30 3c 3d 61 2d 31 26 26 61 2d 31 3c .if(0<=a-1&&a-1<
0890: 57 29 20 72 65 71 20 3d 20 6d 61 78 28 72 65 71 W) req = max(req
08a0: 2c 20 62 75 5b 79 5d 5b 61 2d 31 5d 2b 31 29 3b , bu[y][a-1]+1);
08b0: 0d 0a 09 09 09 09 09 69 66 28 30 3c 3d 79 2b 31 .......if(0<=y+1
08c0: 26 26 79 2b 31 3c 48 29 20 72 65 71 20 3d 20 6d &&y+1<H) req = m
08d0: 61 78 28 72 65 71 2c 20 62 75 5b 79 2b 31 5d 5b ax(req, bu[y+1][
08e0: 61 5d 2b 31 29 3b 0d 0a 09 09 09 09 09 69 66 28 a]+1);.......if(
08f0: 66 69 78 65 64 5b 79 5d 5b 61 5d 29 20 7b 0d 0a fixed[y][a]) {..
0900: 09 09 09 09 09 09 69 66 28 66 69 78 65 64 5b 79 ......if(fixed[y
0910: 5d 5b 61 5d 20 3c 20 72 65 71 29 0d 0a 09 09 09 ][a] < req).....
0920: 09 09 09 09 67 6f 74 6f 20 6c 61 62 65 6c 5f 62 ....goto label_b
0930: 75 5f 65 6e 64 3b 0d 0a 09 09 09 09 09 09 62 75 u_end;........bu
0940: 5b 79 5d 5b 61 5d 20 3d 20 66 69 78 65 64 5b 79 [y][a] = fixed[y
0950: 5d 5b 61 5d 3b 0d 0a 09 09 09 09 09 7d 20 65 6c ][a];.......} el
0960: 73 65 20 7b 0d 0a 09 09 09 09 09 09 62 75 5b 79 se {........bu[y
0970: 5d 5b 61 5d 20 3d 20 72 65 71 3b 0d 0a 09 09 09 ][a] = req;.....
0980: 09 09 7d 0d 0a 09 09 09 09 7d 0d 0a 09 09 09 09 ..}......}......
0990: 66 6f 72 28 69 6e 74 20 61 3d 57 2d 31 3b 20 61 for(int a=W-1; a
09a0: 3e 78 3b 20 2d 2d 61 29 20 7b 0d 0a 09 09 09 09 >x; --a) {......
09b0: 09 69 6e 74 20 72 65 71 20 3d 20 31 3b 0d 0a 09 .int req = 1;...
09c0: 09 09 09 09 69 66 28 30 3c 3d 61 2b 31 26 26 61 ....if(0<=a+1&&a
09d0: 2b 31 3c 57 29 20 72 65 71 20 3d 20 6d 61 78 28 +1<W) req = max(
09e0: 72 65 71 2c 20 62 75 5b 79 5d 5b 61 2b 31 5d 2b req, bu[y][a+1]+
09f0: 31 29 3b 0d 0a 09 09 09 09 09 69 66 28 30 3c 3d 1);.......if(0<=
0a00: 79 2b 31 26 26 79 2b 31 3c 48 29 20 72 65 71 20 y+1&&y+1<H) req
0a10: 3d 20 6d 61 78 28 72 65 71 2c 20 62 75 5b 79 2b = max(req, bu[y+
0a20: 31 5d 5b 61 5d 2b 31 29 3b 0d 0a 09 09 09 09 09 1][a]+1);.......
0a30: 69 66 28 66 69 78 65 64 5b 79 5d 5b 61 5d 29 20 if(fixed[y][a])
0a40: 7b 0d 0a 09 09 09 09 09 09 69 66 28 66 69 78 65 {........if(fixe
0a50: 64 5b 79 5d 5b 61 5d 20 3c 20 72 65 71 29 0d 0a d[y][a] < req)..
0a60: 09 09 09 09 09 09 09 67 6f 74 6f 20 6c 61 62 65 .......goto labe
0a70: 6c 5f 62 75 5f 65 6e 64 3b 0d 0a 09 09 09 09 09 l_bu_end;.......
0a80: 09 62 75 5b 79 5d 5b 61 5d 20 3d 20 66 69 78 65 .bu[y][a] = fixe
0a90: 64 5b 79 5d 5b 61 5d 3b 0d 0a 09 09 09 09 09 7d d[y][a];.......}
0aa0: 20 65 6c 73 65 20 7b 0d 0a 09 09 09 09 09 09 62 else {........b
0ab0: 75 5b 79 5d 5b 61 5d 20 3d 20 72 65 71 3b 0d 0a u[y][a] = req;..
0ac0: 09 09 09 09 09 7d 0d 0a 09 09 09 09 7d 0d 0a 09 .....}......}...
0ad0: 09 09 09 69 6e 74 20 61 20 3d 20 78 3b 0d 0a 09 ...int a = x;...
0ae0: 09 09 09 7b 0d 0a 09 09 09 09 09 69 6e 74 20 72 ...{.......int r
0af0: 65 71 20 3d 20 31 3b 0d 0a 09 09 09 09 09 69 66 eq = 1;.......if
0b00: 28 30 3c 3d 61 2d 31 26 26 61 2d 31 3c 57 29 20 (0<=a-1&&a-1<W)
0b10: 72 65 71 20 3d 20 6d 61 78 28 72 65 71 2c 20 62 req = max(req, b
0b20: 75 5b 79 5d 5b 61 2d 31 5d 2b 31 29 3b 0d 0a 09 u[y][a-1]+1);...
0b30: 09 09 09 09 69 66 28 30 3c 3d 61 2b 31 26 26 61 ....if(0<=a+1&&a
0b40: 2b 31 3c 57 29 20 72 65 71 20 3d 20 6d 61 78 28 +1<W) req = max(
0b50: 72 65 71 2c 20 62 75 5b 79 5d 5b 61 2b 31 5d 2b req, bu[y][a+1]+
0b60: 31 29 3b 0d 0a 09 09 09 09 09 69 66 28 30 3c 3d 1);.......if(0<=
0b70: 79 2b 31 26 26 79 2b 31 3c 48 29 20 72 65 71 20 y+1&&y+1<H) req
0b80: 3d 20 6d 61 78 28 72 65 71 2c 20 62 75 5b 79 2b = max(req, bu[y+
0b90: 31 5d 5b 61 5d 2b 31 29 3b 0d 0a 09 09 09 09 09 1][a]+1);.......
0ba0: 69 66 28 66 69 78 65 64 5b 79 5d 5b 61 5d 29 20 if(fixed[y][a])
0bb0: 7b 0d 0a 09 09 09 09 09 09 69 66 28 66 69 78 65 {........if(fixe
0bc0: 64 5b 79 5d 5b 61 5d 20 3c 20 72 65 71 29 0d 0a d[y][a] < req)..
0bd0: 09 09 09 09 09 09 09 67 6f 74 6f 20 6c 61 62 65 .......goto labe
0be0: 6c 5f 62 75 5f 65 6e 64 3b 0d 0a 09 09 09 09 09 l_bu_end;.......
0bf0: 09 62 75 5b 79 5d 5b 61 5d 20 3d 20 66 69 78 65 .bu[y][a] = fixe
0c00: 64 5b 79 5d 5b 61 5d 3b 0d 0a 09 09 09 09 09 7d d[y][a];.......}
0c10: 20 65 6c 73 65 20 7b 0d 0a 09 09 09 09 09 09 62 else {........b
0c20: 75 5b 79 5d 5b 61 5d 20 3d 20 72 65 71 3b 0d 0a u[y][a] = req;..
0c30: 09 09 09 09 09 7d 0d 0a 09 09 09 09 7d 0d 0a 09 .....}......}...
0c40: 09 09 09 62 75 5f 73 75 6d 5b 79 5d 20 3d 20 61 ...bu_sum[y] = a
0c50: 63 63 75 6d 75 6c 61 74 65 28 62 75 5b 79 5d 2e ccumulate(bu[y].
0c60: 62 65 67 69 6e 28 29 2c 20 62 75 5b 79 5d 2e 65 begin(), bu[y].e
0c70: 6e 64 28 29 2c 20 30 29 3b 0d 0a 09 09 09 09 62 nd(), 0);......b
0c80: 75 5f 62 65 67 69 6e 20 2d 2d 3b 0d 0a 09 09 09 u_begin --;.....
0c90: 7d 0d 0a 09 09 6c 61 62 65 6c 5f 62 75 5f 65 6e }....label_bu_en
0ca0: 64 3a 3b 0d 0a 0d 0a 09 09 09 69 66 28 74 64 5f d:;.......if(td_
0cb0: 65 6e 64 20 3c 3d 20 62 75 5f 62 65 67 69 6e 29 end <= bu_begin)
0cc0: 0d 0a 09 09 09 09 63 6f 6e 74 69 6e 75 65 3b 0d ......continue;.
0cd0: 0a 0d 0a 09 09 09 69 6e 74 20 62 61 73 65 6c 69 ......int baseli
0ce0: 6e 65 20 3d 20 30 3b 0d 0a 09 09 09 66 6f 72 28 ne = 0;.....for(
0cf0: 69 6e 74 20 59 3d 30 3b 20 59 3c 48 3b 20 2b 2b int Y=0; Y<H; ++
0d00: 59 29 0d 0a 09 09 09 09 62 61 73 65 6c 69 6e 65 Y)......baseline
0d10: 20 2b 3d 20 28 59 3c 62 75 5f 62 65 67 69 6e 20 += (Y<bu_begin
0d20: 3f 20 74 64 5f 73 75 6d 5b 59 5d 20 3a 20 59 3d ? td_sum[Y] : Y=
0d30: 3d 62 75 5f 62 65 67 69 6e 20 3f 20 30 20 3a 20 =bu_begin ? 0 :
0d40: 62 75 5f 73 75 6d 5b 59 5d 29 3b 0d 0a 0d 0a 09 bu_sum[Y]);.....
0d50: 09 09 66 6f 72 28 69 6e 74 20 79 3d 62 75 5f 62 ..for(int y=bu_b
0d60: 65 67 69 6e 3b 20 79 3c 74 64 5f 65 6e 64 3b 20 egin; y<td_end;
0d70: 2b 2b 79 29 0d 0a 09 09 09 7b 0d 0a 09 09 09 09 ++y).....{......
0d80: 69 6e 74 20 73 63 6f 72 65 20 3d 20 62 61 73 65 int score = base
0d90: 6c 69 6e 65 3b 0d 0a 09 09 09 09 66 6f 72 28 69 line;......for(i
0da0: 6e 74 20 78 3d 30 3b 20 78 3c 57 3b 20 2b 2b 78 nt x=0; x<W; ++x
0db0: 29 0d 0a 09 09 09 09 09 73 63 6f 72 65 20 2b 3d ).......score +=
0dc0: 20 6d 61 78 28 74 64 5b 79 5d 5b 78 5d 2c 20 62 max(td[y][x], b
0dd0: 75 5b 79 5d 5b 78 5d 29 3b 0d 0a 09 09 09 09 62 u[y][x]);......b
0de0: 65 73 74 20 3d 20 6d 69 6e 28 62 65 73 74 2c 20 est = min(best,
0df0: 73 63 6f 72 65 29 3b 0d 0a 09 09 09 09 69 66 28 score);......if(
0e00: 79 3c 48 29 0d 0a 09 09 09 09 09 62 61 73 65 6c y<H).......basel
0e10: 69 6e 65 20 2b 3d 20 74 64 5f 73 75 6d 5b 79 5d ine += td_sum[y]
0e20: 20 2d 20 62 75 5f 73 75 6d 5b 79 2b 31 5d 3b 0d - bu_sum[y+1];.
0e30: 0a 09 09 09 7d 0d 0a 09 09 7d 0d 0a 09 09 72 65 ....}....}....re
0e40: 74 75 72 6e 20 28 62 65 73 74 3d 3d 49 4e 46 20 turn (best==INF
0e50: 3f 20 2d 31 20 3a 20 62 65 73 74 29 3b 0d 0a 09 ? -1 : best);...
0e60: 7d 0d 0a 7d 3b 0d 0a 0d 0a 2f 2f 20 42 45 47 49 }..};....// BEGI
0e70: 4e 20 43 55 54 20 48 45 52 45 0d 0a 23 69 6e 63 N CUT HERE..#inc
0e80: 6c 75 64 65 20 3c 63 74 69 6d 65 3e 0d 0a 64 6f lude <ctime>..do
0e90: 75 62 6c 65 20 73 74 61 72 74 5f 74 69 6d 65 3b uble start_time;
0ea0: 20 73 74 72 69 6e 67 20 74 69 6d 65 72 28 29 0d string timer().
0eb0: 0a 20 7b 20 6f 73 74 72 69 6e 67 73 74 72 65 61 . { ostringstrea
0ec0: 6d 20 6f 73 3b 20 6f 73 20 3c 3c 20 22 20 28 22 m os; os << " ("
0ed0: 20 3c 3c 20 69 6e 74 28 28 63 6c 6f 63 6b 28 29 << int((clock()
0ee0: 2d 73 74 61 72 74 5f 74 69 6d 65 29 2f 43 4c 4f -start_time)/CLO
0ef0: 43 4b 53 5f 50 45 52 5f 53 45 43 2a 31 30 30 30 CKS_PER_SEC*1000
0f00: 29 20 3c 3c 20 22 20 6d 73 65 63 29 22 3b 20 72 ) << " msec)"; r
0f10: 65 74 75 72 6e 20 6f 73 2e 73 74 72 28 29 3b 20 eturn os.str();
0f20: 7d 0d 0a 74 65 6d 70 6c 61 74 65 3c 74 79 70 65 }..template<type
0f30: 6e 61 6d 65 20 54 3e 20 6f 73 74 72 65 61 6d 26 name T> ostream&
0f40: 20 6f 70 65 72 61 74 6f 72 3c 3c 28 6f 73 74 72 operator<<(ostr
0f50: 65 61 6d 26 20 6f 73 2c 20 63 6f 6e 73 74 20 76 eam& os, const v
0f60: 65 63 74 6f 72 3c 54 3e 26 20 76 29 0d 0a 20 7b ector<T>& v).. {
0f70: 20 6f 73 20 3c 3c 20 22 7b 20 22 3b 0d 0a 20 20 os << "{ ";..
0f80: 20 66 6f 72 28 74 79 70 65 6e 61 6d 65 20 76 65 for(typename ve
0f90: 63 74 6f 72 3c 54 3e 3a 3a 63 6f 6e 73 74 5f 69 ctor<T>::const_i
0fa0: 74 65 72 61 74 6f 72 20 69 74 3d 76 2e 62 65 67 terator it=v.beg
0fb0: 69 6e 28 29 3b 20 69 74 21 3d 76 2e 65 6e 64 28 in(); it!=v.end(
0fc0: 29 3b 20 2b 2b 69 74 29 0d 0a 20 20 20 6f 73 20 ); ++it).. os
0fd0: 3c 3c 20 27 5c 22 27 20 3c 3c 20 2a 69 74 20 3c << '\"' << *it <
0fe0: 3c 20 27 5c 22 27 20 3c 3c 20 28 69 74 2b 31 3d < '\"' << (it+1=
0ff0: 3d 76 2e 65 6e 64 28 29 20 3f 20 22 22 20 3a 20 =v.end() ? "" :
1000: 22 2c 20 22 29 3b 20 6f 73 20 3c 3c 20 22 20 7d ", "); os << " }
1010: 22 3b 20 72 65 74 75 72 6e 20 6f 73 3b 20 7d 0d "; return os; }.
1020: 0a 76 6f 69 64 20 76 65 72 69 66 79 5f 63 61 73 .void verify_cas
1030: 65 28 63 6f 6e 73 74 20 69 6e 74 26 20 45 78 70 e(const int& Exp
1040: 65 63 74 65 64 2c 20 63 6f 6e 73 74 20 69 6e 74 ected, const int
1050: 26 20 52 65 63 65 69 76 65 64 29 20 7b 0d 0a 20 & Received) {..
1060: 62 6f 6f 6c 20 6f 6b 20 3d 20 28 45 78 70 65 63 bool ok = (Expec
1070: 74 65 64 20 3d 3d 20 52 65 63 65 69 76 65 64 29 ted == Received)
1080: 3b 0d 0a 20 69 66 28 6f 6b 29 20 63 65 72 72 20 ;.. if(ok) cerr
1090: 3c 3c 20 22 50 41 53 53 45 44 22 20 3c 3c 20 74 << "PASSED" << t
10a0: 69 6d 65 72 28 29 20 3c 3c 20 65 6e 64 6c 3b 20 imer() << endl;
10b0: 20 65 6c 73 65 20 7b 20 63 65 72 72 20 3c 3c 20 else { cerr <<
10c0: 22 46 41 49 4c 45 44 22 20 3c 3c 20 74 69 6d 65 "FAILED" << time
10d0: 72 28 29 20 3c 3c 20 65 6e 64 6c 3b 0d 0a 20 63 r() << endl;.. c
10e0: 65 72 72 20 3c 3c 20 22 5c 74 6f 3a 20 5c 22 22 err << "\to: \""
10f0: 20 3c 3c 20 45 78 70 65 63 74 65 64 20 3c 3c 20 << Expected <<
1100: 27 5c 22 27 20 3c 3c 20 65 6e 64 6c 20 3c 3c 20 '\"' << endl <<
1110: 22 5c 74 78 3a 20 5c 22 22 20 3c 3c 20 52 65 63 "\tx: \"" << Rec
1120: 65 69 76 65 64 20 3c 3c 20 27 5c 22 27 20 3c 3c eived << '\"' <<
1130: 20 65 6e 64 6c 3b 20 7d 20 7d 0d 0a 23 64 65 66 endl; } }..#def
1140: 69 6e 65 20 43 41 53 45 28 4e 29 20 7b 63 65 72 ine CASE(N) {cer
1150: 72 20 3c 3c 20 22 54 65 73 74 20 43 61 73 65 20 r << "Test Case
1160: 23 22 20 3c 3c 20 4e 20 3c 3c 20 22 2e 2e 2e 22 #" << N << "..."
1170: 20 3c 3c 20 66 6c 75 73 68 3b 20 73 74 61 72 74 << flush; start
1180: 5f 74 69 6d 65 3d 63 6c 6f 63 6b 28 29 3b 0d 0a _time=clock();..
1190: 23 64 65 66 69 6e 65 20 45 4e 44 09 20 76 65 72 #define END. ver
11a0: 69 66 79 5f 63 61 73 65 28 5f 2c 20 54 68 65 4d ify_case(_, TheM
11b0: 6f 75 6e 74 61 69 6e 28 29 2e 6d 69 6e 53 75 6d ountain().minSum
11c0: 28 6e 2c 20 6d 2c 20 72 6f 77 49 6e 64 65 78 2c (n, m, rowIndex,
11d0: 20 63 6f 6c 75 6d 6e 49 6e 64 65 78 2c 20 65 6c columnIndex, el
11e0: 65 6d 65 6e 74 29 29 3b 7d 0d 0a 69 6e 74 20 6d ement));}..int m
11f0: 61 69 6e 28 29 7b 0d 0a 0d 0a 43 41 53 45 28 30 ain(){....CASE(0
1200: 29 0d 0a 09 69 6e 74 20 6e 20 3d 20 32 3b 20 0d )...int n = 2; .
1210: 0a 09 69 6e 74 20 6d 20 3d 20 33 3b 20 0d 0a 09 ..int m = 3; ...
1220: 69 6e 74 20 72 6f 77 49 6e 64 65 78 5f 5b 5d 20 int rowIndex_[]
1230: 3d 20 7b 30 2c 20 30 2c 20 30 2c 20 31 2c 20 31 = {0, 0, 0, 1, 1
1240: 2c 20 31 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 , 1};... vector
1250: 20 3c 69 6e 74 3e 20 72 6f 77 49 6e 64 65 78 28 <int> rowIndex(
1260: 72 6f 77 49 6e 64 65 78 5f 2c 20 72 6f 77 49 6e rowIndex_, rowIn
1270: 64 65 78 5f 2b 73 69 7a 65 6f 66 28 72 6f 77 49 dex_+sizeof(rowI
1280: 6e 64 65 78 5f 29 2f 73 69 7a 65 6f 66 28 2a 72 ndex_)/sizeof(*r
1290: 6f 77 49 6e 64 65 78 5f 29 29 3b 20 0d 0a 09 69 owIndex_)); ...i
12a0: 6e 74 20 63 6f 6c 75 6d 6e 49 6e 64 65 78 5f 5b nt columnIndex_[
12b0: 5d 20 3d 20 7b 30 2c 20 31 2c 20 32 2c 20 30 2c ] = {0, 1, 2, 0,
12c0: 20 31 2c 20 32 7d 3b 0d 0a 09 20 20 76 65 63 74 1, 2};... vect
12d0: 6f 72 20 3c 69 6e 74 3e 20 63 6f 6c 75 6d 6e 49 or <int> columnI
12e0: 6e 64 65 78 28 63 6f 6c 75 6d 6e 49 6e 64 65 78 ndex(columnIndex
12f0: 5f 2c 20 63 6f 6c 75 6d 6e 49 6e 64 65 78 5f 2b _, columnIndex_+
1300: 73 69 7a 65 6f 66 28 63 6f 6c 75 6d 6e 49 6e 64 sizeof(columnInd
1310: 65 78 5f 29 2f 73 69 7a 65 6f 66 28 2a 63 6f 6c ex_)/sizeof(*col
1320: 75 6d 6e 49 6e 64 65 78 5f 29 29 3b 20 0d 0a 09 umnIndex_)); ...
1330: 69 6e 74 20 65 6c 65 6d 65 6e 74 5f 5b 5d 20 3d int element_[] =
1340: 20 7b 34 2c 20 36 2c 20 39 2c 20 31 2c 20 33 2c {4, 6, 9, 1, 3,
1350: 20 36 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 6};... vector
1360: 3c 69 6e 74 3e 20 65 6c 65 6d 65 6e 74 28 65 6c <int> element(el
1370: 65 6d 65 6e 74 5f 2c 20 65 6c 65 6d 65 6e 74 5f ement_, element_
1380: 2b 73 69 7a 65 6f 66 28 65 6c 65 6d 65 6e 74 5f +sizeof(element_
1390: 29 2f 73 69 7a 65 6f 66 28 2a 65 6c 65 6d 65 6e )/sizeof(*elemen
13a0: 74 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 5f 20 3d t_)); ...int _ =
13b0: 20 32 39 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 29; ..END..CASE
13c0: 28 31 29 0d 0a 09 69 6e 74 20 6e 20 3d 20 32 3b (1)...int n = 2;
13d0: 20 0d 0a 09 69 6e 74 20 6d 20 3d 20 33 3b 20 0d ...int m = 3; .
13e0: 0a 09 69 6e 74 20 72 6f 77 49 6e 64 65 78 5f 5b ..int rowIndex_[
13f0: 5d 20 3d 20 7b 31 2c 20 30 2c 20 31 7d 3b 0d 0a ] = {1, 0, 1};..
1400: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
1410: 72 6f 77 49 6e 64 65 78 28 72 6f 77 49 6e 64 65 rowIndex(rowInde
1420: 78 5f 2c 20 72 6f 77 49 6e 64 65 78 5f 2b 73 69 x_, rowIndex_+si
1430: 7a 65 6f 66 28 72 6f 77 49 6e 64 65 78 5f 29 2f zeof(rowIndex_)/
1440: 73 69 7a 65 6f 66 28 2a 72 6f 77 49 6e 64 65 78 sizeof(*rowIndex
1450: 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 63 6f 6c 75 _)); ...int colu
1460: 6d 6e 49 6e 64 65 78 5f 5b 5d 20 3d 20 7b 32 2c mnIndex_[] = {2,
1470: 20 32 2c 20 30 7d 3b 0d 0a 09 20 20 76 65 63 74 2, 0};... vect
1480: 6f 72 20 3c 69 6e 74 3e 20 63 6f 6c 75 6d 6e 49 or <int> columnI
1490: 6e 64 65 78 28 63 6f 6c 75 6d 6e 49 6e 64 65 78 ndex(columnIndex
14a0: 5f 2c 20 63 6f 6c 75 6d 6e 49 6e 64 65 78 5f 2b _, columnIndex_+
14b0: 73 69 7a 65 6f 66 28 63 6f 6c 75 6d 6e 49 6e 64 sizeof(columnInd
14c0: 65 78 5f 29 2f 73 69 7a 65 6f 66 28 2a 63 6f 6c ex_)/sizeof(*col
14d0: 75 6d 6e 49 6e 64 65 78 5f 29 29 3b 20 0d 0a 09 umnIndex_)); ...
14e0: 69 6e 74 20 65 6c 65 6d 65 6e 74 5f 5b 5d 20 3d int element_[] =
14f0: 20 7b 35 2c 20 37 2c 20 36 7d 3b 0d 0a 09 20 20 {5, 7, 6};...
1500: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 65 6c 65 vector <int> ele
1510: 6d 65 6e 74 28 65 6c 65 6d 65 6e 74 5f 2c 20 65 ment(element_, e
1520: 6c 65 6d 65 6e 74 5f 2b 73 69 7a 65 6f 66 28 65 lement_+sizeof(e
1530: 6c 65 6d 65 6e 74 5f 29 2f 73 69 7a 65 6f 66 28 lement_)/sizeof(
1540: 2a 65 6c 65 6d 65 6e 74 5f 29 29 3b 20 0d 0a 09 *element_)); ...
1550: 69 6e 74 20 5f 20 3d 20 34 30 3b 20 0d 0a 45 4e int _ = 40; ..EN
1560: 44 0d 0a 43 41 53 45 28 32 29 0d 0a 09 69 6e 74 D..CASE(2)...int
1570: 20 6e 20 3d 20 33 3b 20 0d 0a 09 69 6e 74 20 6d n = 3; ...int m
1580: 20 3d 20 33 3b 20 0d 0a 09 69 6e 74 20 72 6f 77 = 3; ...int row
1590: 49 6e 64 65 78 5f 5b 5d 20 3d 20 7b 30 2c 20 30 Index_[] = {0, 0
15a0: 2c 20 32 2c 20 32 7d 3b 0d 0a 09 20 20 76 65 63 , 2, 2};... vec
15b0: 74 6f 72 20 3c 69 6e 74 3e 20 72 6f 77 49 6e 64 tor <int> rowInd
15c0: 65 78 28 72 6f 77 49 6e 64 65 78 5f 2c 20 72 6f ex(rowIndex_, ro
15d0: 77 49 6e 64 65 78 5f 2b 73 69 7a 65 6f 66 28 72 wIndex_+sizeof(r
15e0: 6f 77 49 6e 64 65 78 5f 29 2f 73 69 7a 65 6f 66 owIndex_)/sizeof
15f0: 28 2a 72 6f 77 49 6e 64 65 78 5f 29 29 3b 20 0d (*rowIndex_)); .
1600: 0a 09 69 6e 74 20 63 6f 6c 75 6d 6e 49 6e 64 65 ..int columnInde
1610: 78 5f 5b 5d 20 3d 20 7b 30 2c 20 32 2c 20 32 2c x_[] = {0, 2, 2,
1620: 20 30 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 0};... vector
1630: 3c 69 6e 74 3e 20 63 6f 6c 75 6d 6e 49 6e 64 65 <int> columnInde
1640: 78 28 63 6f 6c 75 6d 6e 49 6e 64 65 78 5f 2c 20 x(columnIndex_,
1650: 63 6f 6c 75 6d 6e 49 6e 64 65 78 5f 2b 73 69 7a columnIndex_+siz
1660: 65 6f 66 28 63 6f 6c 75 6d 6e 49 6e 64 65 78 5f eof(columnIndex_
1670: 29 2f 73 69 7a 65 6f 66 28 2a 63 6f 6c 75 6d 6e )/sizeof(*column
1680: 49 6e 64 65 78 5f 29 29 3b 20 0d 0a 09 69 6e 74 Index_)); ...int
1690: 20 65 6c 65 6d 65 6e 74 5f 5b 5d 20 3d 20 7b 31 element_[] = {1
16a0: 2c 20 31 2c 20 31 2c 20 31 7d 3b 0d 0a 09 20 20 , 1, 1, 1};...
16b0: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 65 6c 65 vector <int> ele
16c0: 6d 65 6e 74 28 65 6c 65 6d 65 6e 74 5f 2c 20 65 ment(element_, e
16d0: 6c 65 6d 65 6e 74 5f 2b 73 69 7a 65 6f 66 28 65 lement_+sizeof(e
16e0: 6c 65 6d 65 6e 74 5f 29 2f 73 69 7a 65 6f 66 28 lement_)/sizeof(
16f0: 2a 65 6c 65 6d 65 6e 74 5f 29 29 3b 20 0d 0a 09 *element_)); ...
1700: 69 6e 74 20 5f 20 3d 20 31 35 3b 20 0d 0a 45 4e int _ = 15; ..EN
1710: 44 0d 0a 43 41 53 45 28 33 29 0d 0a 09 69 6e 74 D..CASE(3)...int
1720: 20 6e 20 3d 20 32 3b 20 0d 0a 09 69 6e 74 20 6d n = 2; ...int m
1730: 20 3d 20 32 3b 20 0d 0a 09 69 6e 74 20 72 6f 77 = 2; ...int row
1740: 49 6e 64 65 78 5f 5b 5d 20 3d 20 7b 30 2c 20 30 Index_[] = {0, 0
1750: 2c 20 31 2c 20 31 7d 3b 0d 0a 09 20 20 76 65 63 , 1, 1};... vec
1760: 74 6f 72 20 3c 69 6e 74 3e 20 72 6f 77 49 6e 64 tor <int> rowInd
1770: 65 78 28 72 6f 77 49 6e 64 65 78 5f 2c 20 72 6f ex(rowIndex_, ro
1780: 77 49 6e 64 65 78 5f 2b 73 69 7a 65 6f 66 28 72 wIndex_+sizeof(r
1790: 6f 77 49 6e 64 65 78 5f 29 2f 73 69 7a 65 6f 66 owIndex_)/sizeof
17a0: 28 2a 72 6f 77 49 6e 64 65 78 5f 29 29 3b 20 0d (*rowIndex_)); .
17b0: 0a 09 69 6e 74 20 63 6f 6c 75 6d 6e 49 6e 64 65 ..int columnInde
17c0: 78 5f 5b 5d 20 3d 20 7b 30 2c 20 31 2c 20 31 2c x_[] = {0, 1, 1,
17d0: 20 30 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 0};... vector
17e0: 3c 69 6e 74 3e 20 63 6f 6c 75 6d 6e 49 6e 64 65 <int> columnInde
17f0: 78 28 63 6f 6c 75 6d 6e 49 6e 64 65 78 5f 2c 20 x(columnIndex_,
1800: 63 6f 6c 75 6d 6e 49 6e 64 65 78 5f 2b 73 69 7a columnIndex_+siz
1810: 65 6f 66 28 63 6f 6c 75 6d 6e 49 6e 64 65 78 5f eof(columnIndex_
1820: 29 2f 73 69 7a 65 6f 66 28 2a 63 6f 6c 75 6d 6e )/sizeof(*column
1830: 49 6e 64 65 78 5f 29 29 3b 20 0d 0a 09 69 6e 74 Index_)); ...int
1840: 20 65 6c 65 6d 65 6e 74 5f 5b 5d 20 3d 20 7b 35 element_[] = {5
1850: 2c 20 38 2c 20 35 2c 20 38 7d 3b 0d 0a 09 20 20 , 8, 5, 8};...
1860: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 65 6c 65 vector <int> ele
1870: 6d 65 6e 74 28 65 6c 65 6d 65 6e 74 5f 2c 20 65 ment(element_, e
1880: 6c 65 6d 65 6e 74 5f 2b 73 69 7a 65 6f 66 28 65 lement_+sizeof(e
1890: 6c 65 6d 65 6e 74 5f 29 2f 73 69 7a 65 6f 66 28 lement_)/sizeof(
18a0: 2a 65 6c 65 6d 65 6e 74 5f 29 29 3b 20 0d 0a 09 *element_)); ...
18b0: 69 6e 74 20 5f 20 3d 20 2d 31 3b 20 0d 0a 45 4e int _ = -1; ..EN
18c0: 44 0d 0a 43 41 53 45 28 34 29 0d 0a 09 69 6e 74 D..CASE(4)...int
18d0: 20 6e 20 3d 20 31 3b 20 0d 0a 09 69 6e 74 20 6d n = 1; ...int m
18e0: 20 3d 20 33 3b 20 0d 0a 09 69 6e 74 20 72 6f 77 = 3; ...int row
18f0: 49 6e 64 65 78 5f 5b 5d 20 3d 20 7b 30 7d 3b 0d Index_[] = {0};.
1900: 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e .. vector <int>
1910: 20 72 6f 77 49 6e 64 65 78 28 72 6f 77 49 6e 64 rowIndex(rowInd
1920: 65 78 5f 2c 20 72 6f 77 49 6e 64 65 78 5f 2b 73 ex_, rowIndex_+s
1930: 69 7a 65 6f 66 28 72 6f 77 49 6e 64 65 78 5f 29 izeof(rowIndex_)
1940: 2f 73 69 7a 65 6f 66 28 2a 72 6f 77 49 6e 64 65 /sizeof(*rowInde
1950: 78 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 63 6f 6c x_)); ...int col
1960: 75 6d 6e 49 6e 64 65 78 5f 5b 5d 20 3d 20 7b 31 umnIndex_[] = {1
1970: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 };... vector <i
1980: 6e 74 3e 20 63 6f 6c 75 6d 6e 49 6e 64 65 78 28 nt> columnIndex(
1990: 63 6f 6c 75 6d 6e 49 6e 64 65 78 5f 2c 20 63 6f columnIndex_, co
19a0: 6c 75 6d 6e 49 6e 64 65 78 5f 2b 73 69 7a 65 6f lumnIndex_+sizeo
19b0: 66 28 63 6f 6c 75 6d 6e 49 6e 64 65 78 5f 29 2f f(columnIndex_)/
19c0: 73 69 7a 65 6f 66 28 2a 63 6f 6c 75 6d 6e 49 6e sizeof(*columnIn
19d0: 64 65 78 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 65 dex_)); ...int e
19e0: 6c 65 6d 65 6e 74 5f 5b 5d 20 3d 20 7b 31 7d 3b lement_[] = {1};
19f0: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 ... vector <int
1a00: 3e 20 65 6c 65 6d 65 6e 74 28 65 6c 65 6d 65 6e > element(elemen
1a10: 74 5f 2c 20 65 6c 65 6d 65 6e 74 5f 2b 73 69 7a t_, element_+siz
1a20: 65 6f 66 28 65 6c 65 6d 65 6e 74 5f 29 2f 73 69 eof(element_)/si
1a30: 7a 65 6f 66 28 2a 65 6c 65 6d 65 6e 74 5f 29 29 zeof(*element_))
1a40: 3b 20 0d 0a 09 69 6e 74 20 5f 20 3d 20 2d 31 3b ; ...int _ = -1;
1a50: 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 35 29 0d ..END..CASE(5).
1a60: 0a 09 69 6e 74 20 6e 20 3d 20 31 32 33 3b 20 0d ..int n = 123; .
1a70: 0a 09 69 6e 74 20 6d 20 3d 20 34 35 3b 20 0d 0a ..int m = 45; ..
1a80: 09 69 6e 74 20 72 6f 77 49 6e 64 65 78 5f 5b 5d .int rowIndex_[]
1a90: 20 3d 20 7b 32 2c 20 33 2c 20 35 2c 20 37 2c 20 = {2, 3, 5, 7,
1aa0: 31 31 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 11};... vector
1ab0: 3c 69 6e 74 3e 20 72 6f 77 49 6e 64 65 78 28 72 <int> rowIndex(r
1ac0: 6f 77 49 6e 64 65 78 5f 2c 20 72 6f 77 49 6e 64 owIndex_, rowInd
1ad0: 65 78 5f 2b 73 69 7a 65 6f 66 28 72 6f 77 49 6e ex_+sizeof(rowIn
1ae0: 64 65 78 5f 29 2f 73 69 7a 65 6f 66 28 2a 72 6f dex_)/sizeof(*ro
1af0: 77 49 6e 64 65 78 5f 29 29 3b 20 0d 0a 09 69 6e wIndex_)); ...in
1b00: 74 20 63 6f 6c 75 6d 6e 49 6e 64 65 78 5f 5b 5d t columnIndex_[]
1b10: 20 3d 20 7b 31 33 2c 20 31 37 2c 20 31 39 2c 20 = {13, 17, 19,
1b20: 32 33 2c 20 32 39 7d 3b 0d 0a 09 20 20 76 65 63 23, 29};... vec
1b30: 74 6f 72 20 3c 69 6e 74 3e 20 63 6f 6c 75 6d 6e tor <int> column
1b40: 49 6e 64 65 78 28 63 6f 6c 75 6d 6e 49 6e 64 65 Index(columnInde
1b50: 78 5f 2c 20 63 6f 6c 75 6d 6e 49 6e 64 65 78 5f x_, columnIndex_
1b60: 2b 73 69 7a 65 6f 66 28 63 6f 6c 75 6d 6e 49 6e +sizeof(columnIn
1b70: 64 65 78 5f 29 2f 73 69 7a 65 6f 66 28 2a 63 6f dex_)/sizeof(*co
1b80: 6c 75 6d 6e 49 6e 64 65 78 5f 29 29 3b 20 0d 0a lumnIndex_)); ..
1b90: 09 69 6e 74 20 65 6c 65 6d 65 6e 74 5f 5b 5d 20 .int element_[]
1ba0: 3d 20 7b 31 30 30 2c 20 32 30 30 2c 20 33 30 30 = {100, 200, 300
1bb0: 2c 20 34 30 30 2c 20 35 30 30 7d 3b 0d 0a 09 20 , 400, 500};...
1bc0: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 65 6c vector <int> el
1bd0: 65 6d 65 6e 74 28 65 6c 65 6d 65 6e 74 5f 2c 20 ement(element_,
1be0: 65 6c 65 6d 65 6e 74 5f 2b 73 69 7a 65 6f 66 28 element_+sizeof(
1bf0: 65 6c 65 6d 65 6e 74 5f 29 2f 73 69 7a 65 6f 66 element_)/sizeof
1c00: 28 2a 65 6c 65 6d 65 6e 74 5f 29 29 3b 20 0d 0a (*element_)); ..
1c10: 09 69 6e 74 20 5f 20 3d 20 33 36 37 30 34 37 3b .int _ = 367047;
1c20: 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 36 29 0d ..END..CASE(6).
1c30: 0a 09 69 6e 74 20 6e 20 3d 20 32 30 30 3b 20 0d ..int n = 200; .
1c40: 0a 09 69 6e 74 20 6d 20 3d 20 32 30 30 3b 20 0d ..int m = 200; .
1c50: 0a 09 69 6e 74 20 72 6f 77 49 6e 64 65 78 5f 5b ..int rowIndex_[
1c60: 5d 20 3d 20 7b 35 7d 3b 0d 0a 09 20 20 76 65 63 ] = {5};... vec
1c70: 74 6f 72 20 3c 69 6e 74 3e 20 72 6f 77 49 6e 64 tor <int> rowInd
1c80: 65 78 28 72 6f 77 49 6e 64 65 78 5f 2c 20 72 6f ex(rowIndex_, ro
1c90: 77 49 6e 64 65 78 5f 2b 73 69 7a 65 6f 66 28 72 wIndex_+sizeof(r
1ca0: 6f 77 49 6e 64 65 78 5f 29 2f 73 69 7a 65 6f 66 owIndex_)/sizeof
1cb0: 28 2a 72 6f 77 49 6e 64 65 78 5f 29 29 3b 20 0d (*rowIndex_)); .
1cc0: 0a 09 69 6e 74 20 63 6f 6c 75 6d 6e 49 6e 64 65 ..int columnInde
1cd0: 78 5f 5b 5d 20 3d 20 7b 38 7d 3b 0d 0a 09 20 20 x_[] = {8};...
1ce0: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 63 6f 6c vector <int> col
1cf0: 75 6d 6e 49 6e 64 65 78 28 63 6f 6c 75 6d 6e 49 umnIndex(columnI
1d00: 6e 64 65 78 5f 2c 20 63 6f 6c 75 6d 6e 49 6e 64 ndex_, columnInd
1d10: 65 78 5f 2b 73 69 7a 65 6f 66 28 63 6f 6c 75 6d ex_+sizeof(colum
1d20: 6e 49 6e 64 65 78 5f 29 2f 73 69 7a 65 6f 66 28 nIndex_)/sizeof(
1d30: 2a 63 6f 6c 75 6d 6e 49 6e 64 65 78 5f 29 29 3b *columnIndex_));
1d40: 20 0d 0a 09 69 6e 74 20 65 6c 65 6d 65 6e 74 5f ...int element_
1d50: 5b 5d 20 3d 20 7b 36 36 36 7d 3b 0d 0a 09 20 20 [] = {666};...
1d60: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 65 6c 65 vector <int> ele
1d70: 6d 65 6e 74 28 65 6c 65 6d 65 6e 74 5f 2c 20 65 ment(element_, e
1d80: 6c 65 6d 65 6e 74 5f 2b 73 69 7a 65 6f 66 28 65 lement_+sizeof(e
1d90: 6c 65 6d 65 6e 74 5f 29 2f 73 69 7a 65 6f 66 28 lement_)/sizeof(
1da0: 2a 65 6c 65 6d 65 6e 74 5f 29 29 3b 20 0d 0a 09 *element_)); ...
1db0: 69 6e 74 20 5f 20 3d 20 35 37 33 37 35 35 34 3b int _ = 5737554;
1dc0: 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 37 29 0d ..END..CASE(7).
1dd0: 0a 09 69 6e 74 20 6e 20 3d 20 31 30 3b 20 0d 0a ..int n = 10; ..
1de0: 09 69 6e 74 20 6d 20 3d 20 31 30 3b 20 0d 0a 09 .int m = 10; ...
1df0: 69 6e 74 20 72 6f 77 49 6e 64 65 78 5f 5b 5d 20 int rowIndex_[]
1e00: 3d 20 7b 30 2c 20 38 2c 20 37 7d 3b 0d 0a 09 20 = {0, 8, 7};...
1e10: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 72 6f vector <int> ro
1e20: 77 49 6e 64 65 78 28 72 6f 77 49 6e 64 65 78 5f wIndex(rowIndex_
1e30: 2c 20 72 6f 77 49 6e 64 65 78 5f 2b 73 69 7a 65 , rowIndex_+size
1e40: 6f 66 28 72 6f 77 49 6e 64 65 78 5f 29 2f 73 69 of(rowIndex_)/si
1e50: 7a 65 6f 66 28 2a 72 6f 77 49 6e 64 65 78 5f 29 zeof(*rowIndex_)
1e60: 29 3b 20 0d 0a 09 69 6e 74 20 63 6f 6c 75 6d 6e ); ...int column
1e70: 49 6e 64 65 78 5f 5b 5d 20 3d 20 7b 33 2c 20 31 Index_[] = {3, 1
1e80: 2c 20 39 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 , 9};... vector
1e90: 20 3c 69 6e 74 3e 20 63 6f 6c 75 6d 6e 49 6e 64 <int> columnInd
1ea0: 65 78 28 63 6f 6c 75 6d 6e 49 6e 64 65 78 5f 2c ex(columnIndex_,
1eb0: 20 63 6f 6c 75 6d 6e 49 6e 64 65 78 5f 2b 73 69 columnIndex_+si
1ec0: 7a 65 6f 66 28 63 6f 6c 75 6d 6e 49 6e 64 65 78 zeof(columnIndex
1ed0: 5f 29 2f 73 69 7a 65 6f 66 28 2a 63 6f 6c 75 6d _)/sizeof(*colum
1ee0: 6e 49 6e 64 65 78 5f 29 29 3b 20 0d 0a 09 69 6e nIndex_)); ...in
1ef0: 74 20 65 6c 65 6d 65 6e 74 5f 5b 5d 20 3d 20 7b t element_[] = {
1f00: 35 2c 20 34 2c 20 37 7d 3b 0d 0a 09 20 20 76 65 5, 4, 7};... ve
1f10: 63 74 6f 72 20 3c 69 6e 74 3e 20 65 6c 65 6d 65 ctor <int> eleme
1f20: 6e 74 28 65 6c 65 6d 65 6e 74 5f 2c 20 65 6c 65 nt(element_, ele
1f30: 6d 65 6e 74 5f 2b 73 69 7a 65 6f 66 28 65 6c 65 ment_+sizeof(ele
1f40: 6d 65 6e 74 5f 29 2f 73 69 7a 65 6f 66 28 2a 65 ment_)/sizeof(*e
1f50: 6c 65 6d 65 6e 74 5f 29 29 3b 20 0d 0a 09 69 6e lement_)); ...in
1f60: 74 20 5f 20 3d 20 35 39 33 3b 20 0d 0a 45 4e 44 t _ = 593; ..END
1f70: 0d 0a 43 41 53 45 28 38 29 0d 0a 09 69 6e 74 20 ..CASE(8)...int
1f80: 6e 20 3d 20 32 30 30 3b 20 0d 0a 09 69 6e 74 20 n = 200; ...int
1f90: 6d 20 3d 20 32 30 30 3b 20 0d 0a 09 69 6e 74 20 m = 200; ...int
1fa0: 72 6f 77 49 6e 64 65 78 5f 5b 5d 20 3d 20 7b 31 rowIndex_[] = {1
1fb0: 32 39 2c 39 39 2c 31 34 32 2c 33 33 2c 31 31 31 29,99,142,33,111
1fc0: 2c 31 37 34 2c 31 36 39 2c 31 37 36 2c 38 33 2c ,174,169,176,83,
1fd0: 31 34 33 2c 37 30 2c 31 31 36 2c 31 39 33 2c 31 143,70,116,193,1
1fe0: 33 39 2c 37 2c 33 35 2c 31 31 31 2c 34 2c 31 38 39,7,35,111,4,18
1ff0: 39 2c 31 31 31 2c 31 37 30 2c 32 39 2c 31 36 2c 9,111,170,29,16,
2000: 38 37 2c 31 31 35 2c 34 2c 36 30 2c 37 31 2c 33 87,115,4,60,71,3
2010: 37 2c 31 33 38 2c 31 32 38 2c 33 38 2c 36 31 2c 7,138,128,38,61,
2020: 31 37 36 2c 31 38 37 2c 36 36 2c 36 34 2c 38 34 176,187,66,64,84
2030: 2c 31 32 30 2c 31 30 34 2c 31 32 34 2c 31 32 39 ,120,104,124,129
2040: 2c 39 31 2c 31 33 37 2c 31 31 34 2c 31 38 37 2c ,91,137,114,187,
2050: 39 37 2c 31 31 35 2c 31 35 31 2c 31 34 30 7d 3b 97,115,151,140};
2060: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 ... vector <int
2070: 3e 20 72 6f 77 49 6e 64 65 78 28 72 6f 77 49 6e > rowIndex(rowIn
2080: 64 65 78 5f 2c 20 72 6f 77 49 6e 64 65 78 5f 2b dex_, rowIndex_+
2090: 73 69 7a 65 6f 66 28 72 6f 77 49 6e 64 65 78 5f sizeof(rowIndex_
20a0: 29 2f 73 69 7a 65 6f 66 28 2a 72 6f 77 49 6e 64 )/sizeof(*rowInd
20b0: 65 78 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 63 6f ex_)); ...int co
20c0: 6c 75 6d 6e 49 6e 64 65 78 5f 5b 5d 20 3d 20 7b lumnIndex_[] = {
20d0: 31 39 31 2c 31 34 38 2c 31 39 34 2c 31 33 2c 39 191,148,194,13,9
20e0: 30 2c 31 37 2c 31 38 35 2c 31 36 33 2c 31 37 2c 0,17,185,163,17,
20f0: 31 37 30 2c 31 39 33 2c 31 36 35 2c 31 34 30 2c 170,193,165,140,
2100: 31 35 38 2c 38 35 2c 31 35 2c 35 36 2c 39 31 2c 158,85,15,56,91,
2110: 39 2c 36 38 2c 31 35 33 2c 38 33 2c 39 2c 39 37 9,68,153,83,9,97
2120: 2c 37 34 2c 34 30 2c 31 36 30 2c 31 36 35 2c 34 ,74,40,160,165,4
2130: 39 2c 31 35 31 2c 31 37 33 2c 39 38 2c 31 32 33 9,151,173,98,123
2140: 2c 34 34 2c 31 33 39 2c 31 36 34 2c 36 36 2c 31 ,44,139,164,66,1
2150: 31 32 2c 31 34 31 2c 31 37 32 2c 39 31 2c 31 34 12,141,172,91,14
2160: 37 2c 37 31 2c 31 36 37 2c 31 32 33 2c 35 33 2c 7,71,167,123,53,
2170: 31 38 39 2c 38 36 2c 37 31 2c 31 37 31 7d 3b 0d 189,86,71,171};.
2180: 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e .. vector <int>
2190: 20 63 6f 6c 75 6d 6e 49 6e 64 65 78 28 63 6f 6c columnIndex(col
21a0: 75 6d 6e 49 6e 64 65 78 5f 2c 20 63 6f 6c 75 6d umnIndex_, colum
21b0: 6e 49 6e 64 65 78 5f 2b 73 69 7a 65 6f 66 28 63 nIndex_+sizeof(c
21c0: 6f 6c 75 6d 6e 49 6e 64 65 78 5f 29 2f 73 69 7a olumnIndex_)/siz
21d0: 65 6f 66 28 2a 63 6f 6c 75 6d 6e 49 6e 64 65 78 eof(*columnIndex
21e0: 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 65 6c 65 6d _)); ...int elem
21f0: 65 6e 74 5f 5b 5d 20 3d 20 7b 39 35 33 2c 32 31 ent_[] = {953,21
2200: 36 2c 33 30 37 2c 31 39 37 2c 39 37 30 2c 35 39 6,307,197,970,59
2210: 30 2c 36 35 39 2c 31 35 33 2c 37 39 2c 32 36 32 0,659,153,79,262
2220: 2c 36 32 38 2c 31 35 33 2c 31 30 36 2c 39 30 34 ,628,153,106,904
2230: 2c 38 38 38 2c 32 34 39 2c 32 32 34 2c 38 33 39 ,888,249,224,839
2240: 2c 32 39 2c 33 32 37 2c 36 36 34 2c 36 31 39 2c ,29,327,664,619,
2250: 33 38 37 2c 33 32 35 2c 38 36 35 2c 38 34 39 2c 387,325,865,849,
2260: 35 31 36 2c 33 31 33 2c 36 34 39 2c 31 33 35 2c 516,313,649,135,
2270: 37 31 33 2c 35 38 35 2c 33 34 37 2c 32 37 39 2c 713,585,347,279,
2280: 37 30 32 2c 38 33 37 2c 36 38 32 2c 38 31 37 2c 702,837,682,817,
2290: 38 34 34 2c 39 38 31 2c 34 30 31 2c 34 31 30 2c 844,981,401,410,
22a0: 39 38 32 2c 38 39 31 2c 31 36 37 2c 31 30 32 2c 982,891,167,102,
22b0: 36 34 36 2c 37 33 2c 37 38 34 2c 34 35 35 7d 3b 646,73,784,455};
22c0: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 ... vector <int
22d0: 3e 20 65 6c 65 6d 65 6e 74 28 65 6c 65 6d 65 6e > element(elemen
22e0: 74 5f 2c 20 65 6c 65 6d 65 6e 74 5f 2b 73 69 7a t_, element_+siz
22f0: 65 6f 66 28 65 6c 65 6d 65 6e 74 5f 29 2f 73 69 eof(element_)/si
2300: 7a 65 6f 66 28 2a 65 6c 65 6d 65 6e 74 5f 29 29 zeof(*element_))
2310: 3b 20 0d 0a 09 69 6e 74 20 5f 20 3d 20 2d 31 3b ; ...int _ = -1;
2320: 20 0d 0a 45 4e 44 0d 0a 2f 2a 0d 0a 43 41 53 45 ..END../*..CASE
2330: 28 39 29 0d 0a 09 69 6e 74 20 6e 20 3d 20 3b 20 (9)...int n = ;
2340: 0d 0a 09 69 6e 74 20 6d 20 3d 20 3b 20 0d 0a 09 ...int m = ; ...
2350: 69 6e 74 20 72 6f 77 49 6e 64 65 78 5f 5b 5d 20 int rowIndex_[]
2360: 3d 20 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c = ;... vector <
2370: 69 6e 74 3e 20 72 6f 77 49 6e 64 65 78 28 72 6f int> rowIndex(ro
2380: 77 49 6e 64 65 78 5f 2c 20 72 6f 77 49 6e 64 65 wIndex_, rowInde
2390: 78 5f 2b 73 69 7a 65 6f 66 28 72 6f 77 49 6e 64 x_+sizeof(rowInd
23a0: 65 78 5f 29 2f 73 69 7a 65 6f 66 28 2a 72 6f 77 ex_)/sizeof(*row
23b0: 49 6e 64 65 78 5f 29 29 3b 20 0d 0a 09 69 6e 74 Index_)); ...int
23c0: 20 63 6f 6c 75 6d 6e 49 6e 64 65 78 5f 5b 5d 20 columnIndex_[]
23d0: 3d 20 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c = ;... vector <
23e0: 69 6e 74 3e 20 63 6f 6c 75 6d 6e 49 6e 64 65 78 int> columnIndex
23f0: 28 63 6f 6c 75 6d 6e 49 6e 64 65 78 5f 2c 20 63 (columnIndex_, c
2400: 6f 6c 75 6d 6e 49 6e 64 65 78 5f 2b 73 69 7a 65 olumnIndex_+size
2410: 6f 66 28 63 6f 6c 75 6d 6e 49 6e 64 65 78 5f 29 of(columnIndex_)
2420: 2f 73 69 7a 65 6f 66 28 2a 63 6f 6c 75 6d 6e 49 /sizeof(*columnI
2430: 6e 64 65 78 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 ndex_)); ...int
2440: 65 6c 65 6d 65 6e 74 5f 5b 5d 20 3d 20 3b 0d 0a element_[] = ;..
2450: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
2460: 65 6c 65 6d 65 6e 74 28 65 6c 65 6d 65 6e 74 5f element(element_
2470: 2c 20 65 6c 65 6d 65 6e 74 5f 2b 73 69 7a 65 6f , element_+sizeo
2480: 66 28 65 6c 65 6d 65 6e 74 5f 29 2f 73 69 7a 65 f(element_)/size
2490: 6f 66 28 2a 65 6c 65 6d 65 6e 74 5f 29 29 3b 20 of(*element_));
24a0: 0d 0a 09 69 6e 74 20 5f 20 3d 20 3b 20 0d 0a 45 ...int _ = ; ..E
24b0: 4e 44 0d 0a 2a 2f 0d 0a 7d 0d 0a 2f 2f 20 45 4e ND..*/..}..// EN
24c0: 44 20 43 55 54 20 48 45 52 45 0d 0a D CUT HERE..