6b700c1e67 2013-06-04 kinaba: #include <iostream> 6b700c1e67 2013-06-04 kinaba: #include <sstream> 6b700c1e67 2013-06-04 kinaba: #include <iomanip> 6b700c1e67 2013-06-04 kinaba: #include <vector> 6b700c1e67 2013-06-04 kinaba: #include <string> 6b700c1e67 2013-06-04 kinaba: #include <map> 6b700c1e67 2013-06-04 kinaba: #include <set> 6b700c1e67 2013-06-04 kinaba: #include <algorithm> 6b700c1e67 2013-06-04 kinaba: #include <numeric> 6b700c1e67 2013-06-04 kinaba: #include <iterator> 6b700c1e67 2013-06-04 kinaba: #include <functional> 6b700c1e67 2013-06-04 kinaba: #include <complex> 6b700c1e67 2013-06-04 kinaba: #include <queue> 6b700c1e67 2013-06-04 kinaba: #include <stack> 6b700c1e67 2013-06-04 kinaba: #include <cmath> 6b700c1e67 2013-06-04 kinaba: #include <cassert> 6b700c1e67 2013-06-04 kinaba: using namespace std; 6b700c1e67 2013-06-04 kinaba: typedef long long LL; 6b700c1e67 2013-06-04 kinaba: typedef long double LD; 6b700c1e67 2013-06-04 kinaba: typedef complex<double> CMP; 6b700c1e67 2013-06-04 kinaba: 6b700c1e67 2013-06-04 kinaba: class WallGameDiv1 { public: 6b700c1e67 2013-06-04 kinaba: int play(vector <string> costs) 6b700c1e67 2013-06-04 kinaba: { 6b700c1e67 2013-06-04 kinaba: int H = costs.size(); 6b700c1e67 2013-06-04 kinaba: int W = costs[0].size(); 6b700c1e67 2013-06-04 kinaba: vector<vector<int> > C(H, vector<int>(W)); 6b700c1e67 2013-06-04 kinaba: for(int y=0; y<H; ++y) 6b700c1e67 2013-06-04 kinaba: for(int x=0; x<W; ++x) 6b700c1e67 2013-06-04 kinaba: C[y][x] = costs[y][x] = '0'; 6b700c1e67 2013-06-04 kinaba: 6b700c1e67 2013-06-04 kinaba: vector<vector<int> > dp(H, vector<int>(W)); 6b700c1e67 2013-06-04 kinaba: for(int x=0; x<W; ++x) 6b700c1e67 2013-06-04 kinaba: dp[H-1][x] = C[H-1][x]; 6b700c1e67 2013-06-04 kinaba: 6b700c1e67 2013-06-04 kinaba: // dp[y][x] = what is the score of entering C[y] from [x]?? 6b700c1e67 2013-06-04 kinaba: for(int y=H-2; y>=0; --y) 6b700c1e67 2013-06-04 kinaba: for(int x=0; x<W; ++x) 6b700c1e67 2013-06-04 kinaba: { 6b700c1e67 2013-06-04 kinaba: int le = lefty(C[y], dp[y+1], x); 6b700c1e67 2013-06-04 kinaba: vector<int> CC = C[y], DD = dp[y+1]; 6b700c1e67 2013-06-04 kinaba: reverse(CC.begin(), CC.end()); 6b700c1e67 2013-06-04 kinaba: reverse(DD.begin(), DD.end()); 6b700c1e67 2013-06-04 kinaba: int ri = lefty(CC, DD, W-1-x); 6b700c1e67 2013-06-04 kinaba: 6b700c1e67 2013-06-04 kinaba: if(min(le, ri) < dp[y+1][x]) 6b700c1e67 2013-06-04 kinaba: dp[y][x] = C[y][x] + dp[y+1][x]; 6b700c1e67 2013-06-04 kinaba: else 6b700c1e67 2013-06-04 kinaba: dp[y][x] = C[y][x] + min(le, ri); 6b700c1e67 2013-06-04 kinaba: // no blocking score 6b700c1e67 2013-06-04 kinaba: vector<int> s = dp[y+1]; 6b700c1e67 2013-06-04 kinaba: s[x] += C[y][x]; 6b700c1e67 2013-06-04 kinaba: for(int p=C[y][x], xx=x-1; xx>=0; --xx) 6b700c1e67 2013-06-04 kinaba: s[xx] += (p += C[y][xx]); 6b700c1e67 2013-06-04 kinaba: for(int p=C[y][x], xx=x+1; xx<W; ++xx) 6b700c1e67 2013-06-04 kinaba: s[xx] += (p += C[y][xx]); 6b700c1e67 2013-06-04 kinaba: } 6b700c1e67 2013-06-04 kinaba: return *min_element(dp[0].begin(), dp[0].end()); 6b700c1e67 2013-06-04 kinaba: } 6b700c1e67 2013-06-04 kinaba: 6b700c1e67 2013-06-04 kinaba: int lefty(const vector<int>& cur, const vector<int>& down, const int S) 6b700c1e67 2013-06-04 kinaba: { 6b700c1e67 2013-06-04 kinaba: // best score when moved to left from S first; 6b700c1e67 2013-06-04 kinaba: return -1; 6b700c1e67 2013-06-04 kinaba: } 6b700c1e67 2013-06-04 kinaba: }; 6b700c1e67 2013-06-04 kinaba: 6b700c1e67 2013-06-04 kinaba: // BEGIN CUT HERE 6b700c1e67 2013-06-04 kinaba: #include <ctime> 6b700c1e67 2013-06-04 kinaba: double start_time; string timer() 6b700c1e67 2013-06-04 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 6b700c1e67 2013-06-04 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 6b700c1e67 2013-06-04 kinaba: { os << "{ "; 6b700c1e67 2013-06-04 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 6b700c1e67 2013-06-04 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 6b700c1e67 2013-06-04 kinaba: void verify_case(const int& Expected, const int& Received) { 6b700c1e67 2013-06-04 kinaba: bool ok = (Expected == Received); 6b700c1e67 2013-06-04 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 6b700c1e67 2013-06-04 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 6b700c1e67 2013-06-04 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 6b700c1e67 2013-06-04 kinaba: #define END verify_case(_, WallGameDiv1().play(costs));} 6b700c1e67 2013-06-04 kinaba: int main(){ 6b700c1e67 2013-06-04 kinaba: 6b700c1e67 2013-06-04 kinaba: CASE(0) 6b700c1e67 2013-06-04 kinaba: string costs_[] = {"12" 6b700c1e67 2013-06-04 kinaba: ,"34"}; 6b700c1e67 2013-06-04 kinaba: vector <string> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 6b700c1e67 2013-06-04 kinaba: int _ = 6; 6b700c1e67 2013-06-04 kinaba: END 6b700c1e67 2013-06-04 kinaba: CASE(1) 6b700c1e67 2013-06-04 kinaba: string costs_[] = {"99999" 6b700c1e67 2013-06-04 kinaba: ,"99999" 6b700c1e67 2013-06-04 kinaba: ,"99999"}; 6b700c1e67 2013-06-04 kinaba: vector <string> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 6b700c1e67 2013-06-04 kinaba: int _ = 99; 6b700c1e67 2013-06-04 kinaba: END 6b700c1e67 2013-06-04 kinaba: CASE(2) 6b700c1e67 2013-06-04 kinaba: string costs_[] = {"11111" 6b700c1e67 2013-06-04 kinaba: ,"90005"}; 6b700c1e67 2013-06-04 kinaba: vector <string> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 6b700c1e67 2013-06-04 kinaba: int _ = 10; 6b700c1e67 2013-06-04 kinaba: END 6b700c1e67 2013-06-04 kinaba: CASE(3) 6b700c1e67 2013-06-04 kinaba: string costs_[] = {"4417231387449337370319219832088987579792" 6b700c1e67 2013-06-04 kinaba: ,"3117295688208899006196193430472892512797" 6b700c1e67 2013-06-04 kinaba: ,"0835796222361526836944954410684516919758" 6b700c1e67 2013-06-04 kinaba: ,"1988200069973565052900745230547016216225" 6b700c1e67 2013-06-04 kinaba: ,"8080511471118865780390486996601082102418" 6b700c1e67 2013-06-04 kinaba: ,"4229084185957675819725844582167613108400" 6b700c1e67 2013-06-04 kinaba: ,"9068653877952162764545674979144308771754" 6b700c1e67 2013-06-04 kinaba: ,"8551565425951612499712254182109991511690" 6b700c1e67 2013-06-04 kinaba: ,"7090525592007482152807163656647658543093" 6b700c1e67 2013-06-04 kinaba: ,"9198968742256995592729889137556032960142" 6b700c1e67 2013-06-04 kinaba: ,"2071864379877766468141740053503050313101" 6b700c1e67 2013-06-04 kinaba: ,"1055375249261868472993219156394129253481" 6b700c1e67 2013-06-04 kinaba: ,"2461178270502857106406495509025426298874" 6b700c1e67 2013-06-04 kinaba: ,"8216781259733537757203421037984512664825" 6b700c1e67 2013-06-04 kinaba: ,"4693452554407216935375049784445568498482" 6b700c1e67 2013-06-04 kinaba: ,"2709693439640250842244170297203200674391" 6b700c1e67 2013-06-04 kinaba: ,"5122217695676372684217182241705137947908" 6b700c1e67 2013-06-04 kinaba: ,"6668814191410691246849638388008228444294" 6b700c1e67 2013-06-04 kinaba: ,"4952122070212780440963814752538149378639" 6b700c1e67 2013-06-04 kinaba: ,"9827737761436134120332969866554332504400" 6b700c1e67 2013-06-04 kinaba: ,"3412406588339828249986707470540386748886" 6b700c1e67 2013-06-04 kinaba: ,"7521506848088506994554600408372456405830" 6b700c1e67 2013-06-04 kinaba: ,"1916926179183007872881163173153907665999" 6b700c1e67 2013-06-04 kinaba: ,"6636166791472761992310264951474925339024" 6b700c1e67 2013-06-04 kinaba: ,"6679667717747231380196787943691121008076" 6b700c1e67 2013-06-04 kinaba: ,"3218993234115685151069259138068533004433" 6b700c1e67 2013-06-04 kinaba: ,"4920152552986426962081492913852060211795" 6b700c1e67 2013-06-04 kinaba: ,"0365186235986445521382132973036266396894" 6b700c1e67 2013-06-04 kinaba: ,"3205351414936828189305188614651974318855" 6b700c1e67 2013-06-04 kinaba: ,"3144278971529524658788277656125598825426" 6b700c1e67 2013-06-04 kinaba: ,"5525287537572356662391582052968411726245" 6b700c1e67 2013-06-04 kinaba: ,"2130137226726919525622574701068062252930" 6b700c1e67 2013-06-04 kinaba: ,"2369996694245544770519574837226971226841" 6b700c1e67 2013-06-04 kinaba: ,"6806769058165410189286521891570936341547" 6b700c1e67 2013-06-04 kinaba: ,"0448109211631660241710734664066810078242" 6b700c1e67 2013-06-04 kinaba: ,"4622919135804954122810530631429501069659" 6b700c1e67 2013-06-04 kinaba: ,"0235247446548732490429856705369583140671" 6b700c1e67 2013-06-04 kinaba: ,"2193399741215975228987754171460722199304" 6b700c1e67 2013-06-04 kinaba: ,"1203037020703833716225328076959743850915" 6b700c1e67 2013-06-04 kinaba: ,"5419885193880826109484912489603262199432"}; 6b700c1e67 2013-06-04 kinaba: vector <string> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 6b700c1e67 2013-06-04 kinaba: int _ = 7366; 6b700c1e67 2013-06-04 kinaba: END 6b700c1e67 2013-06-04 kinaba: CASE(4) 6b700c1e67 2013-06-04 kinaba: string costs_[] = ; 6b700c1e67 2013-06-04 kinaba: vector <string> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 6b700c1e67 2013-06-04 kinaba: int _ = ; 6b700c1e67 2013-06-04 kinaba: END 6b700c1e67 2013-06-04 kinaba: CASE(5) 6b700c1e67 2013-06-04 kinaba: string costs_[] = ; 6b700c1e67 2013-06-04 kinaba: vector <string> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 6b700c1e67 2013-06-04 kinaba: int _ = ; 6b700c1e67 2013-06-04 kinaba: END 6b700c1e67 2013-06-04 kinaba: 6b700c1e67 2013-06-04 kinaba: } 6b700c1e67 2013-06-04 kinaba: // END CUT HERE