8166493378 2012-05-12 kinaba: #include <iostream> 8166493378 2012-05-12 kinaba: #include <sstream> 8166493378 2012-05-12 kinaba: #include <iomanip> 8166493378 2012-05-12 kinaba: #include <vector> 8166493378 2012-05-12 kinaba: #include <string> 8166493378 2012-05-12 kinaba: #include <map> 8166493378 2012-05-12 kinaba: #include <set> 8166493378 2012-05-12 kinaba: #include <algorithm> 8166493378 2012-05-12 kinaba: #include <numeric> 8166493378 2012-05-12 kinaba: #include <iterator> 8166493378 2012-05-12 kinaba: #include <functional> 8166493378 2012-05-12 kinaba: #include <complex> 8166493378 2012-05-12 kinaba: #include <queue> 8166493378 2012-05-12 kinaba: #include <stack> 8166493378 2012-05-12 kinaba: #include <cmath> 8166493378 2012-05-12 kinaba: #include <cassert> 8166493378 2012-05-12 kinaba: #include <cstring> 8166493378 2012-05-12 kinaba: #ifdef __GNUC__ 8166493378 2012-05-12 kinaba: #include <ext/hash_map> 8166493378 2012-05-12 kinaba: #define unordered_map __gnu_cxx::hash_map 8166493378 2012-05-12 kinaba: #else 8166493378 2012-05-12 kinaba: #include <unordered_map> 8166493378 2012-05-12 kinaba: #endif 8166493378 2012-05-12 kinaba: using namespace std; 8166493378 2012-05-12 kinaba: typedef long long LL; 8166493378 2012-05-12 kinaba: typedef complex<double> CMP; 8166493378 2012-05-12 kinaba: 8166493378 2012-05-12 kinaba: template<typename T> 8166493378 2012-05-12 kinaba: struct DP3 8166493378 2012-05-12 kinaba: { 8166493378 2012-05-12 kinaba: int N1, N2, N3; 8166493378 2012-05-12 kinaba: vector<T> data; 8166493378 2012-05-12 kinaba: DP3(int N1, int N2, int N3, const T& t = T()) 8166493378 2012-05-12 kinaba: : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<26)); } 8166493378 2012-05-12 kinaba: T& operator()(int i1, int i2, int i3) 8166493378 2012-05-12 kinaba: { return data[ ((i1*N2)+i2)*N3+i3 ]; } 8166493378 2012-05-12 kinaba: void swap(DP3& rhs) 8166493378 2012-05-12 kinaba: { data.swap(rhs.data); } 8166493378 2012-05-12 kinaba: }; 8166493378 2012-05-12 kinaba: 8166493378 2012-05-12 kinaba: class CucumberWatering { public: 8166493378 2012-05-12 kinaba: long long theMin(vector <int> x, int K) 8166493378 2012-05-12 kinaba: { 8166493378 2012-05-12 kinaba: const int N = x.size(); 8166493378 2012-05-12 kinaba: 8166493378 2012-05-12 kinaba: vector<pair<LL,int> > pts; 8166493378 2012-05-12 kinaba: for(int i=0; i<N; ++i) 8166493378 2012-05-12 kinaba: pts.push_back(make_pair(x[i], i)); 8166493378 2012-05-12 kinaba: sort(pts.begin(), pts.end()); 8166493378 2012-05-12 kinaba: 8166493378 2012-05-12 kinaba: DP3<LL> dp(N, K+1, N, -12345678987654321LL); 8166493378 2012-05-12 kinaba: dp(0, 0, 0) = dp(0, 1, 0) = 0; 8166493378 2012-05-12 kinaba: for(int i=1; i<N; ++i) 8166493378 2012-05-12 kinaba: for(int warpUsed=0; warpUsed<=K; ++warpUsed) { 8166493378 2012-05-12 kinaba: for(int lastWarpPt=0; lastWarpPt<i; ++lastWarpPt) 8166493378 2012-05-12 kinaba: dp(i,warpUsed,lastWarpPt) = dp(i-1,warpUsed,lastWarpPt); 8166493378 2012-05-12 kinaba: 8166493378 2012-05-12 kinaba: LL maxGain = 0; 8166493378 2012-05-12 kinaba: if( warpUsed > 1 ) 8166493378 2012-05-12 kinaba: for(int p=0; p<i; ++p) { 8166493378 2012-05-12 kinaba: LL gain = 0; 8166493378 2012-05-12 kinaba: LL P = pts[p].first; 8166493378 2012-05-12 kinaba: LL Q = pts[i].first; 8166493378 2012-05-12 kinaba: for(int k=1; k<N; ++k) { 8166493378 2012-05-12 kinaba: LL X = min(x[k-1], x[k]); 8166493378 2012-05-12 kinaba: LL Y = max(x[k-1], x[k]); 8166493378 2012-05-12 kinaba: gain += max(0LL, (Y-X) - (abs(X-P) + abs(Y-Q))); 8166493378 2012-05-12 kinaba: } 8166493378 2012-05-12 kinaba: maxGain = max(maxGain, dp(i,warpUsed-1,p) + gain); 8166493378 2012-05-12 kinaba: } 8166493378 2012-05-12 kinaba: dp(i,warpUsed,i) = maxGain; 8166493378 2012-05-12 kinaba: } 8166493378 2012-05-12 kinaba: 8166493378 2012-05-12 kinaba: LL naive = 0; 8166493378 2012-05-12 kinaba: for(int i=1; i<N; ++i) 8166493378 2012-05-12 kinaba: naive += abs(LL(x[i-1]) - LL(x[i])); 8166493378 2012-05-12 kinaba: 8166493378 2012-05-12 kinaba: LL maxGain = 0; 8166493378 2012-05-12 kinaba: for(int w=0; w<=K; ++w) 8166493378 2012-05-12 kinaba: for(int p=0; p<N; ++p) 8166493378 2012-05-12 kinaba: maxGain = max(maxGain, dp(N-1,w,p)); 8166493378 2012-05-12 kinaba: 8166493378 2012-05-12 kinaba: return naive - maxGain; 8166493378 2012-05-12 kinaba: } 8166493378 2012-05-12 kinaba: }; 8166493378 2012-05-12 kinaba: 8166493378 2012-05-12 kinaba: // BEGIN CUT HERE 8166493378 2012-05-12 kinaba: #include <ctime> 8166493378 2012-05-12 kinaba: double start_time; string timer() 8166493378 2012-05-12 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 8166493378 2012-05-12 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 8166493378 2012-05-12 kinaba: { os << "{ "; 8166493378 2012-05-12 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 8166493378 2012-05-12 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 8166493378 2012-05-12 kinaba: void verify_case(const long long& Expected, const long long& Received) { 8166493378 2012-05-12 kinaba: bool ok = (Expected == Received); 8166493378 2012-05-12 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 8166493378 2012-05-12 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 8166493378 2012-05-12 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 8166493378 2012-05-12 kinaba: #define END verify_case(_, CucumberWatering().theMin(x, K));} 8166493378 2012-05-12 kinaba: int main(){ 8166493378 2012-05-12 kinaba: 8166493378 2012-05-12 kinaba: CASE(0) 8166493378 2012-05-12 kinaba: int x_[] = {0, 6, 8, 2}; 8166493378 2012-05-12 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 8166493378 2012-05-12 kinaba: int K = 2; 8166493378 2012-05-12 kinaba: long long _ = 6LL; 8166493378 2012-05-12 kinaba: END 8166493378 2012-05-12 kinaba: CASE(1) 8166493378 2012-05-12 kinaba: int x_[] = {-1000000000, 1000000000, 0}; 8166493378 2012-05-12 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 8166493378 2012-05-12 kinaba: int K = 1; 8166493378 2012-05-12 kinaba: long long _ = 3000000000LL; 8166493378 2012-05-12 kinaba: END 8166493378 2012-05-12 kinaba: CASE(2) 8166493378 2012-05-12 kinaba: int x_[] = {58, 2012}; 8166493378 2012-05-12 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 8166493378 2012-05-12 kinaba: int K = 50; 8166493378 2012-05-12 kinaba: long long _ = 0LL; 8166493378 2012-05-12 kinaba: END 8166493378 2012-05-12 kinaba: CASE(3) 8166493378 2012-05-12 kinaba: int x_[] = {9, -3, 14, 6, 5, -9, 32, 7, -5, 26, 2, 11}; 8166493378 2012-05-12 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 8166493378 2012-05-12 kinaba: int K = 3; 8166493378 2012-05-12 kinaba: long long _ = 58LL; 8166493378 2012-05-12 kinaba: END 8166493378 2012-05-12 kinaba: /* 8166493378 2012-05-12 kinaba: CASE(4) 8166493378 2012-05-12 kinaba: int x_[] = ; 8166493378 2012-05-12 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 8166493378 2012-05-12 kinaba: int K = ; 8166493378 2012-05-12 kinaba: long long _ = LL; 8166493378 2012-05-12 kinaba: END 8166493378 2012-05-12 kinaba: CASE(5) 8166493378 2012-05-12 kinaba: int x_[] = ; 8166493378 2012-05-12 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 8166493378 2012-05-12 kinaba: int K = ; 8166493378 2012-05-12 kinaba: long long _ = LL; 8166493378 2012-05-12 kinaba: END 8166493378 2012-05-12 kinaba: */ 8166493378 2012-05-12 kinaba: } 8166493378 2012-05-12 kinaba: // END CUT HERE