Artifact 3c712bb16a6c8631c6da6c5ef8c17e64de41ec5e:
0000: 23 69 6e 63 6c 75 64 65 20 3c 69 6f 73 74 72 65 #include <iostre
0010: 61 6d 3e 20 0d 0a 23 69 6e 63 6c 75 64 65 20 3c am> ..#include <
0020: 73 73 74 72 65 61 6d 3e 20 0d 0a 23 69 6e 63 6c sstream> ..#incl
0030: 75 64 65 20 3c 69 6f 6d 61 6e 69 70 3e 20 0d 0a ude <iomanip> ..
0040: 23 69 6e 63 6c 75 64 65 20 3c 76 65 63 74 6f 72 #include <vector
0050: 3e 20 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 74 > ..#include <st
0060: 72 69 6e 67 3e 20 0d 0a 23 69 6e 63 6c 75 64 65 ring> ..#include
0070: 20 3c 6d 61 70 3e 20 0d 0a 23 69 6e 63 6c 75 64 <map> ..#includ
0080: 65 20 3c 73 65 74 3e 20 0d 0a 23 69 6e 63 6c 75 e <set> ..#inclu
0090: 64 65 20 3c 61 6c 67 6f 72 69 74 68 6d 3e 20 0d de <algorithm> .
00a0: 0a 23 69 6e 63 6c 75 64 65 20 3c 6e 75 6d 65 72 .#include <numer
00b0: 69 63 3e 20 0d 0a 23 69 6e 63 6c 75 64 65 20 3c ic> ..#include <
00c0: 69 74 65 72 61 74 6f 72 3e 20 0d 0a 23 69 6e 63 iterator> ..#inc
00d0: 6c 75 64 65 20 3c 66 75 6e 63 74 69 6f 6e 61 6c lude <functional
00e0: 3e 20 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 6f > ..#include <co
00f0: 6d 70 6c 65 78 3e 20 0d 0a 23 69 6e 63 6c 75 64 mplex> ..#includ
0100: 65 20 3c 71 75 65 75 65 3e 20 0d 0a 23 69 6e 63 e <queue> ..#inc
0110: 6c 75 64 65 20 3c 73 74 61 63 6b 3e 20 0d 0a 23 lude <stack> ..#
0120: 69 6e 63 6c 75 64 65 20 3c 63 6d 61 74 68 3e 20 include <cmath>
0130: 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 61 73 73 ..#include <cass
0140: 65 72 74 3e 20 0d 0a 23 69 6e 63 6c 75 64 65 20 ert> ..#include
0150: 3c 63 73 74 72 69 6e 67 3e 20 0d 0a 75 73 69 6e <cstring> ..usin
0160: 67 20 6e 61 6d 65 73 70 61 63 65 20 73 74 64 3b g namespace std;
0170: 20 0d 0a 74 79 70 65 64 65 66 20 6c 6f 6e 67 20 ..typedef long
0180: 6c 6f 6e 67 20 4c 4c 3b 20 0d 0a 74 79 70 65 64 long LL; ..typed
0190: 65 66 20 63 6f 6d 70 6c 65 78 3c 64 6f 75 62 6c ef complex<doubl
01a0: 65 3e 20 43 4d 50 3b 20 0d 0a 0d 0a 63 6c 61 73 e> CMP; ....clas
01b0: 73 20 43 6f 6e 76 65 78 53 65 71 75 65 6e 63 65 s ConvexSequence
01c0: 20 7b 20 70 75 62 6c 69 63 3a 20 0d 0a 20 20 6c { public: .. l
01d0: 6f 6e 67 20 6c 6f 6e 67 20 67 65 74 4d 69 6e 69 ong long getMini
01e0: 6d 75 6d 28 76 65 63 74 6f 72 20 3c 69 6e 74 3e mum(vector <int>
01f0: 20 61 29 20 0d 0a 20 20 7b 20 0d 0a 20 20 20 20 a) .. { ..
0200: 69 6e 74 20 69 20 3d 20 6d 69 6e 5f 65 6c 65 6d int i = min_elem
0210: 65 6e 74 28 61 2e 62 65 67 69 6e 28 29 2c 20 61 ent(a.begin(), a
0220: 2e 65 6e 64 28 29 29 20 2d 20 61 2e 62 65 67 69 .end()) - a.begi
0230: 6e 28 29 3b 20 0d 0a 20 20 20 20 76 65 63 74 6f n(); .. vecto
0240: 72 3c 4c 4c 3e 20 70 72 65 28 61 2e 62 65 67 69 r<LL> pre(a.begi
0250: 6e 28 29 2c 20 61 2e 62 65 67 69 6e 28 29 2b 69 n(), a.begin()+i
0260: 2b 31 29 3b 20 0d 0a 20 20 20 20 72 65 76 65 72 +1); .. rever
0270: 73 65 28 70 72 65 2e 62 65 67 69 6e 28 29 2c 20 se(pre.begin(),
0280: 70 72 65 2e 65 6e 64 28 29 29 3b 20 0d 0a 20 20 pre.end()); ..
0290: 20 20 76 65 63 74 6f 72 3c 4c 4c 3e 20 70 6f 73 vector<LL> pos
02a0: 74 28 61 2e 62 65 67 69 6e 28 29 2b 69 2c 20 61 t(a.begin()+i, a
02b0: 2e 65 6e 64 28 29 29 3b 20 0d 0a 20 20 20 20 72 .end()); .. r
02c0: 65 74 75 72 6e 20 63 6f 6e 76 65 78 5f 69 6e 63 eturn convex_inc
02d0: 72 28 70 72 65 29 20 2b 20 63 6f 6e 76 65 78 5f r(pre) + convex_
02e0: 69 6e 63 72 28 70 6f 73 74 29 3b 20 0d 0a 20 20 incr(post); ..
02f0: 7d 20 0d 0a 0d 0a 20 20 4c 4c 20 63 6f 6e 76 65 } .... LL conve
0300: 78 5f 69 6e 63 72 28 76 65 63 74 6f 72 3c 4c 4c x_incr(vector<LL
0310: 3e 20 61 29 20 0d 0a 20 20 7b 20 0d 0a 20 20 20 > a) .. { ..
0320: 20 69 66 28 20 61 2e 65 6d 70 74 79 28 29 20 29 if( a.empty() )
0330: 20 20 0d 0a 20 20 20 20 20 20 72 65 74 75 72 6e .. return
0340: 20 30 3b 20 0d 0a 20 20 20 20 66 6f 72 28 69 6e 0; .. for(in
0350: 74 20 69 3d 61 2e 73 69 7a 65 28 29 2d 31 3b 20 t i=a.size()-1;
0360: 69 3e 3d 30 3b 20 2d 2d 69 29 20 0d 0a 20 20 20 i>=0; --i) ..
0370: 20 20 20 61 5b 69 5d 20 2d 3d 20 61 5b 30 5d 3b a[i] -= a[0];
0380: 20 0d 0a 0d 0a 20 20 20 20 4c 4c 20 63 6e 74 20 .... LL cnt
0390: 3d 20 30 3b 20 0d 0a 20 20 20 20 66 6f 72 28 69 = 0; .. for(i
03a0: 6e 74 20 69 3d 31 3b 20 69 3c 61 2e 73 69 7a 65 nt i=1; i<a.size
03b0: 28 29 2d 31 3b 20 2b 2b 69 29 20 0d 0a 20 20 20 ()-1; ++i) ..
03c0: 20 7b 20 0d 0a 20 20 20 20 20 20 4c 4c 20 61 6d { .. LL am
03d0: 61 78 20 3d 20 61 5b 69 5d 3b 20 0d 0a 20 20 20 ax = a[i]; ..
03e0: 20 20 20 66 6f 72 28 69 6e 74 20 6b 3d 69 2b 31 for(int k=i+1
03f0: 3b 20 6b 3c 61 2e 73 69 7a 65 28 29 3b 20 2b 2b ; k<a.size(); ++
0400: 6b 29 20 0d 0a 20 20 20 20 20 20 20 20 61 6d 61 k) .. ama
0410: 78 20 3d 20 6d 69 6e 28 61 6d 61 78 2c 20 28 61 x = min(amax, (a
0420: 5b 6b 5d 20 2d 20 61 5b 69 2d 31 5d 29 20 2f 20 [k] - a[i-1]) /
0430: 28 6b 2d 28 69 2d 31 29 29 20 2b 20 61 5b 69 2d (k-(i-1)) + a[i-
0440: 31 5d 29 3b 20 0d 0a 20 20 20 20 20 20 69 66 28 1]); .. if(
0450: 20 61 6d 61 78 20 3c 20 61 5b 69 5d 20 29 20 7b amax < a[i] ) {
0460: 20 0d 0a 20 20 20 20 20 20 20 20 63 6e 74 20 2b .. cnt +
0470: 3d 20 61 5b 69 5d 2d 61 6d 61 78 3b 20 0d 0a 20 = a[i]-amax; ..
0480: 20 20 20 20 20 20 20 61 5b 69 5d 20 3d 20 61 6d a[i] = am
0490: 61 78 3b 20 0d 0a 20 20 20 20 20 20 7d 20 0d 0a ax; .. } ..
04a0: 20 20 20 20 7d 20 0d 0a 20 20 20 20 72 65 74 75 } .. retu
04b0: 72 6e 20 63 6e 74 3b 20 0d 0a 20 20 7d 20 0d 0a rn cnt; .. } ..
04c0: 7d 3b 20 0d 0a }; ..