Artifact Content
Not logged in

Artifact 1a7c1f0c0f50f317fbc596f30ff6bb34c3c95915


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef complex<double> CMP;

class WallGameDiv1 { public:
	int play(vector <string> costs)
	{
		int H = costs.size();
		int W = costs[0].size();
		vector<vector<int> > C(H, vector<int>(W));
		for(int y=0; y<H; ++y)
		for(int x=0; x<W; ++x)
			C[y][x] = costs[y][x] = '0';

		vector<vector<int> > dp(H, vector<int>(W));
		for(int x=0; x<W; ++x)
			dp[H-1][x] = C[H-1][x];

		// dp[y][x] = what is the score of entering C[y] from [x]??
		for(int y=H-2; y>=0; --y)
		for(int x=0; x<W; ++x)
		{
			int le = lefty(C[y], dp[y+1], x);
			vector<int> CC = C[y], DD = dp[y+1];
			reverse(CC.begin(), CC.end());
			reverse(DD.begin(), DD.end());
			int ri = lefty(CC, DD, W-1-x);

			if(min(le, ri) < dp[y+1][x])
				dp[y][x] = C[y][x] + dp[y+1][x];
			else
				dp[y][x] = C[y][x] + min(le, ri);
			// no blocking score
			vector<int> s = dp[y+1];
			s[x] += C[y][x];
			for(int p=C[y][x], xx=x-1; xx>=0; --xx)
				s[xx] += (p += C[y][xx]);
			for(int p=C[y][x], xx=x+1; xx<W; ++xx)
				s[xx] += (p += C[y][xx]);
		}
		return *min_element(dp[0].begin(), dp[0].end());
	}

	int lefty(const vector<int>& cur, const vector<int>& down, const int S)
	{
		// best score when moved to left from S first;
		return -1;
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, WallGameDiv1().play(costs));}
int main(){

CASE(0)
	string costs_[] = {"12"
,"34"};
	  vector <string> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 
	int _ = 6; 
END
CASE(1)
	string costs_[] = {"99999"
,"99999"
,"99999"};
	  vector <string> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 
	int _ = 99; 
END
CASE(2)
	string costs_[] = {"11111"
,"90005"};
	  vector <string> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 
	int _ = 10; 
END
CASE(3)
	string costs_[] = {"4417231387449337370319219832088987579792"
,"3117295688208899006196193430472892512797"
,"0835796222361526836944954410684516919758"
,"1988200069973565052900745230547016216225"
,"8080511471118865780390486996601082102418"
,"4229084185957675819725844582167613108400"
,"9068653877952162764545674979144308771754"
,"8551565425951612499712254182109991511690"
,"7090525592007482152807163656647658543093"
,"9198968742256995592729889137556032960142"
,"2071864379877766468141740053503050313101"
,"1055375249261868472993219156394129253481"
,"2461178270502857106406495509025426298874"
,"8216781259733537757203421037984512664825"
,"4693452554407216935375049784445568498482"
,"2709693439640250842244170297203200674391"
,"5122217695676372684217182241705137947908"
,"6668814191410691246849638388008228444294"
,"4952122070212780440963814752538149378639"
,"9827737761436134120332969866554332504400"
,"3412406588339828249986707470540386748886"
,"7521506848088506994554600408372456405830"
,"1916926179183007872881163173153907665999"
,"6636166791472761992310264951474925339024"
,"6679667717747231380196787943691121008076"
,"3218993234115685151069259138068533004433"
,"4920152552986426962081492913852060211795"
,"0365186235986445521382132973036266396894"
,"3205351414936828189305188614651974318855"
,"3144278971529524658788277656125598825426"
,"5525287537572356662391582052968411726245"
,"2130137226726919525622574701068062252930"
,"2369996694245544770519574837226971226841"
,"6806769058165410189286521891570936341547"
,"0448109211631660241710734664066810078242"
,"4622919135804954122810530631429501069659"
,"0235247446548732490429856705369583140671"
,"2193399741215975228987754171460722199304"
,"1203037020703833716225328076959743850915"
,"5419885193880826109484912489603262199432"};
	  vector <string> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 
	int _ = 7366; 
END
CASE(4)
	string costs_[] = ;
	  vector <string> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 
	int _ = ; 
END
CASE(5)
	string costs_[] = ;
	  vector <string> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 
	int _ = ; 
END

}
// END CUT HERE