9ce62cec1c 2015-03-26 kinaba: #include <iostream> 9ce62cec1c 2015-03-26 kinaba: #include <sstream> 9ce62cec1c 2015-03-26 kinaba: #include <iomanip> 9ce62cec1c 2015-03-26 kinaba: #include <vector> 9ce62cec1c 2015-03-26 kinaba: #include <string> 9ce62cec1c 2015-03-26 kinaba: #include <map> 9ce62cec1c 2015-03-26 kinaba: #include <set> 9ce62cec1c 2015-03-26 kinaba: #include <algorithm> 9ce62cec1c 2015-03-26 kinaba: #include <numeric> 9ce62cec1c 2015-03-26 kinaba: #include <iterator> 9ce62cec1c 2015-03-26 kinaba: #include <functional> 9ce62cec1c 2015-03-26 kinaba: #include <complex> 9ce62cec1c 2015-03-26 kinaba: #include <queue> 9ce62cec1c 2015-03-26 kinaba: #include <stack> 9ce62cec1c 2015-03-26 kinaba: #include <cmath> 9ce62cec1c 2015-03-26 kinaba: #include <cassert> 9ce62cec1c 2015-03-26 kinaba: #include <tuple> 9ce62cec1c 2015-03-26 kinaba: using namespace std; 9ce62cec1c 2015-03-26 kinaba: typedef long long LL; 9ce62cec1c 2015-03-26 kinaba: 9ce62cec1c 2015-03-26 kinaba: template<typename T> 9ce62cec1c 2015-03-26 kinaba: struct DP2 9ce62cec1c 2015-03-26 kinaba: { 9ce62cec1c 2015-03-26 kinaba: const int N1, N2; 9ce62cec1c 2015-03-26 kinaba: vector<T> data; 9ce62cec1c 2015-03-26 kinaba: DP2(int N1, int N2, const T& t = T()) 9ce62cec1c 2015-03-26 kinaba: : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<(1<<28)); } 9ce62cec1c 2015-03-26 kinaba: T& operator()(int i1, int i2) 9ce62cec1c 2015-03-26 kinaba: { return data[ (i1*N2)+i2 ]; } 9ce62cec1c 2015-03-26 kinaba: void swap(DP2& rhs) 9ce62cec1c 2015-03-26 kinaba: { data.swap(rhs.data); } 9ce62cec1c 2015-03-26 kinaba: }; 9ce62cec1c 2015-03-26 kinaba: 9ce62cec1c 2015-03-26 kinaba: class SuccessiveSubtraction2 { public: 9ce62cec1c 2015-03-26 kinaba: vector <int> calc(vector <int> a, vector <int> p, vector <int> v) 9ce62cec1c 2015-03-26 kinaba: { 9ce62cec1c 2015-03-26 kinaba: vector<int> answer; 9ce62cec1c 2015-03-26 kinaba: for(int i=0; i<p.size(); ++i) { 9ce62cec1c 2015-03-26 kinaba: a[p[i]] = v[i]; 9ce62cec1c 2015-03-26 kinaba: 9ce62cec1c 2015-03-26 kinaba: if(a.size() == 1) { 9ce62cec1c 2015-03-26 kinaba: answer.push_back(a[0]); 9ce62cec1c 2015-03-26 kinaba: continue; 9ce62cec1c 2015-03-26 kinaba: } 9ce62cec1c 2015-03-26 kinaba: 9ce62cec1c 2015-03-26 kinaba: answer.push_back(a[0]-a[1]+solve(a)); 9ce62cec1c 2015-03-26 kinaba: } 9ce62cec1c 2015-03-26 kinaba: return answer; 9ce62cec1c 2015-03-26 kinaba: } 9ce62cec1c 2015-03-26 kinaba: 9ce62cec1c 2015-03-26 kinaba: int solve(const vector<int>& a) 9ce62cec1c 2015-03-26 kinaba: { 9ce62cec1c 2015-03-26 kinaba: DP2<int> dp(a.size(), 5, -0x1fffffff); 9ce62cec1c 2015-03-26 kinaba: dp(1, 0) = 0; 9ce62cec1c 2015-03-26 kinaba: 9ce62cec1c 2015-03-26 kinaba: for(int i=2; i<a.size(); ++i) 9ce62cec1c 2015-03-26 kinaba: for(int prev_s=0; prev_s<=4; ++prev_s) 9ce62cec1c 2015-03-26 kinaba: { 9ce62cec1c 2015-03-26 kinaba: int s = prev_s; 9ce62cec1c 2015-03-26 kinaba: dp(i,s) = max(dp(i,s), dp(i-1,prev_s) + a[i]*(s&1 ? +1 : -1)); 9ce62cec1c 2015-03-26 kinaba: if(prev_s<4) { 9ce62cec1c 2015-03-26 kinaba: s = prev_s + 1; 9ce62cec1c 2015-03-26 kinaba: dp(i,s) = max(dp(i,s), dp(i-1,prev_s) + a[i]*(s&1 ? +1 : -1)); 9ce62cec1c 2015-03-26 kinaba: } 9ce62cec1c 2015-03-26 kinaba: } 9ce62cec1c 2015-03-26 kinaba: 9ce62cec1c 2015-03-26 kinaba: int best = 0; 9ce62cec1c 2015-03-26 kinaba: for(int s=0; s<=4; ++s) 9ce62cec1c 2015-03-26 kinaba: best = max(best, dp(a.size()-1, s)); 9ce62cec1c 2015-03-26 kinaba: return best; 9ce62cec1c 2015-03-26 kinaba: } 9ce62cec1c 2015-03-26 kinaba: }; 9ce62cec1c 2015-03-26 kinaba: 9ce62cec1c 2015-03-26 kinaba: // BEGIN CUT HERE 9ce62cec1c 2015-03-26 kinaba: #include <ctime> 9ce62cec1c 2015-03-26 kinaba: double start_time; string timer() 9ce62cec1c 2015-03-26 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 9ce62cec1c 2015-03-26 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 9ce62cec1c 2015-03-26 kinaba: { os << "{ "; 9ce62cec1c 2015-03-26 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 9ce62cec1c 2015-03-26 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 9ce62cec1c 2015-03-26 kinaba: void verify_case(const vector <int>& Expected, const vector <int>& Received) { 9ce62cec1c 2015-03-26 kinaba: bool ok = (Expected == Received); 9ce62cec1c 2015-03-26 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 9ce62cec1c 2015-03-26 kinaba: cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } 9ce62cec1c 2015-03-26 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 9ce62cec1c 2015-03-26 kinaba: #define END verify_case(_, SuccessiveSubtraction2().calc(a, p, v));} 9ce62cec1c 2015-03-26 kinaba: int main(){ 9ce62cec1c 2015-03-26 kinaba: 9ce62cec1c 2015-03-26 kinaba: CASE(0) 9ce62cec1c 2015-03-26 kinaba: int a_[] = {1, 2, 3, 4, 5}; 9ce62cec1c 2015-03-26 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 9ce62cec1c 2015-03-26 kinaba: int p_[] = {1, 2, 0, 4, 3}; 9ce62cec1c 2015-03-26 kinaba: vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 9ce62cec1c 2015-03-26 kinaba: int v_[] = {3, 9, -10, 5, 1}; 9ce62cec1c 2015-03-26 kinaba: vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 9ce62cec1c 2015-03-26 kinaba: int __[] = {10, 16, 5, 5, 2 }; 9ce62cec1c 2015-03-26 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 9ce62cec1c 2015-03-26 kinaba: END 9ce62cec1c 2015-03-26 kinaba: CASE(1) 9ce62cec1c 2015-03-26 kinaba: int a_[] = {-100, -100, -100, -100, -100}; 9ce62cec1c 2015-03-26 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 9ce62cec1c 2015-03-26 kinaba: int p_[] = {0, 1, 2, 3, 4}; 9ce62cec1c 2015-03-26 kinaba: vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 9ce62cec1c 2015-03-26 kinaba: int v_[] = {0, 0, 0, 0, 0}; 9ce62cec1c 2015-03-26 kinaba: vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 9ce62cec1c 2015-03-26 kinaba: int __[] = {400, 300, 200, 100, 0 }; 9ce62cec1c 2015-03-26 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 9ce62cec1c 2015-03-26 kinaba: END 9ce62cec1c 2015-03-26 kinaba: CASE(2) 9ce62cec1c 2015-03-26 kinaba: int a_[] = {83, 0, 25, 21}; 9ce62cec1c 2015-03-26 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 9ce62cec1c 2015-03-26 kinaba: int p_[] = {0, 3, 2, 1, 3, 1, 2}; 9ce62cec1c 2015-03-26 kinaba: vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 9ce62cec1c 2015-03-26 kinaba: int v_[] = {10, -90, 33, 52, -100, 0, 45}; 9ce62cec1c 2015-03-26 kinaba: vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 9ce62cec1c 2015-03-26 kinaba: int __[] = {56, 125, 133, 81, 91, 143, 155 }; 9ce62cec1c 2015-03-26 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 9ce62cec1c 2015-03-26 kinaba: END 9ce62cec1c 2015-03-26 kinaba: CASE(3) 9ce62cec1c 2015-03-26 kinaba: int a_[] = {1}; 9ce62cec1c 2015-03-26 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 9ce62cec1c 2015-03-26 kinaba: int p_[] = {0, 0, 0, 0}; 9ce62cec1c 2015-03-26 kinaba: vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 9ce62cec1c 2015-03-26 kinaba: int v_[] = {10, -10, 100, -100}; 9ce62cec1c 2015-03-26 kinaba: vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 9ce62cec1c 2015-03-26 kinaba: int __[] = {10, -10, 100, -100 }; 9ce62cec1c 2015-03-26 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 9ce62cec1c 2015-03-26 kinaba: END 9ce62cec1c 2015-03-26 kinaba: CASE(4) 9ce62cec1c 2015-03-26 kinaba: int a_[] = {-11, -4, 28, 38, 21, -29, -45, 11, -58, -39, 92, 35, -56, -6, 29, -2, 61, 10, -29, -63}; 9ce62cec1c 2015-03-26 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 9ce62cec1c 2015-03-26 kinaba: int p_[] = {19, 5, 3, 10, 4, 18, 5, 2, 0, 15}; 9ce62cec1c 2015-03-26 kinaba: vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 9ce62cec1c 2015-03-26 kinaba: int v_[] = {-19, 21, 7, -66, 38, -39, -22, 24, -32, 13}; 9ce62cec1c 2015-03-26 kinaba: vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 9ce62cec1c 2015-03-26 kinaba: int __[] = {451, 443, 412, 440, 457, 467, 468, 464, 443, 458 }; 9ce62cec1c 2015-03-26 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 9ce62cec1c 2015-03-26 kinaba: END 9ce62cec1c 2015-03-26 kinaba: CASE(5) 9ce62cec1c 2015-03-26 kinaba: int a_[] = {10, 20}; 9ce62cec1c 2015-03-26 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 9ce62cec1c 2015-03-26 kinaba: int p_[] = {0, 1}; 9ce62cec1c 2015-03-26 kinaba: vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 9ce62cec1c 2015-03-26 kinaba: int v_[] = {2, 3}; 9ce62cec1c 2015-03-26 kinaba: vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 9ce62cec1c 2015-03-26 kinaba: int __[] = {-18, -1}; 9ce62cec1c 2015-03-26 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 9ce62cec1c 2015-03-26 kinaba: END 9ce62cec1c 2015-03-26 kinaba: /* 9ce62cec1c 2015-03-26 kinaba: CASE(6) 9ce62cec1c 2015-03-26 kinaba: int a_[] = ; 9ce62cec1c 2015-03-26 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 9ce62cec1c 2015-03-26 kinaba: int p_[] = ; 9ce62cec1c 2015-03-26 kinaba: vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 9ce62cec1c 2015-03-26 kinaba: int v_[] = ; 9ce62cec1c 2015-03-26 kinaba: vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 9ce62cec1c 2015-03-26 kinaba: int __[] = ; 9ce62cec1c 2015-03-26 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 9ce62cec1c 2015-03-26 kinaba: END 9ce62cec1c 2015-03-26 kinaba: */ 9ce62cec1c 2015-03-26 kinaba: } 9ce62cec1c 2015-03-26 kinaba: // END CUT HERE