Artifact Content
Not logged in

Artifact 650208ee70c7dd257bfe095766da85d5e93b97f9


#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<LD> CMP;

class FoxAndFlowerShopDivOne { public:
	int theMaxFlowers(vector <string> flowers, int maxDiff)
	{
		int H = flowers.size();
		int W = flowers[0].size();
		vector< vector<int> > s(H+1, vector<int>(W+1));
		vector< vector<int> > d(H+1, vector<int>(W+1));
		for(int y=H-1; y>=0; --y)
		for(int x=W-1; x>=0; --x)
		{
			s[y][x] = s[y+1][x] + s[y][x+1] - s[y+1][x+1] + (flowers[y][x]!='.');
			d[y][x] = d[y+1][x] + d[y][x+1] - d[y+1][x+1] + (flowers[y][x]=='L') - (flowers[y][x]=='P');
		}

		int answer = -1;

		for(int X=1; X<W; ++X)
		{
			map<int, int> d2s_L, d2s_R;

			// left
			for(int y=0; y<H; ++y)
			for(int x=0; x<X; ++x)
			for(int yy=y+1; yy<=H; ++yy)
			for(int xx=x+1; xx<=X; ++xx)
			{
				int ss = s[y][x] - s[yy][x] - s[y][xx] + s[yy][xx];
				int dd = d[y][x] - d[yy][x] - d[y][xx] + d[yy][xx];
				d2s_L[dd] = max(d2s_L[dd], ss);
			}

			// right
			for(int y=0; y<H; ++y)
			for(int x=X; x<W; ++x)
			for(int yy=y+1; yy<=H; ++yy)
			for(int xx=x+1; xx<=W; ++xx)
			{
				int ss = s[y][x] - s[yy][x] - s[y][xx] + s[yy][xx];
				int dd = d[y][x] - d[yy][x] - d[y][xx] + d[yy][xx];
				d2s_R[dd] = max(d2s_R[dd], ss);
			}

			for(map<int,int>::iterator it=d2s_L.begin(); it!=d2s_L.end(); ++it)
			for(map<int,int>::iterator jt=d2s_R.begin(); jt!=d2s_R.end(); ++jt)
				if(abs(it->first + jt->first) <= maxDiff)
					answer = max(answer, it->second + jt->second);
		}

		for(int Y=1; Y<H; ++Y)
		{
			map<int, int> d2s_L, d2s_R;

			// left
			for(int y=0; y<Y; ++y)
			for(int x=0; x<W; ++x)
			for(int yy=y+1; yy<=Y; ++yy)
			for(int xx=x+1; xx<=W; ++xx)
			{
				int ss = s[y][x] - s[yy][x] - s[y][xx] + s[yy][xx];
				int dd = d[y][x] - d[yy][x] - d[y][xx] + d[yy][xx];
				d2s_L[dd] = max(d2s_L[dd], ss);
			}

			// right
			for(int y=Y; y<H; ++y)
			for(int x=0; x<W; ++x)
			for(int yy=y+1; yy<=H; ++yy)
			for(int xx=x+1; xx<=W; ++xx)
			{
				int ss = s[y][x] - s[yy][x] - s[y][xx] + s[yy][xx];
				int dd = d[y][x] - d[yy][x] - d[y][xx] + d[yy][xx];
				d2s_R[dd] = max(d2s_R[dd], ss);
			}

			for(map<int,int>::iterator it=d2s_L.begin(); it!=d2s_L.end(); ++it)
			for(map<int,int>::iterator jt=d2s_R.begin(); jt!=d2s_R.end(); ++jt)
				if(abs(it->first + jt->first) <= maxDiff)
					answer = max(answer, it->second + jt->second);
		}

		return answer;
	}
};

// 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(_, FoxAndFlowerShopDivOne().theMaxFlowers(flowers, maxDiff));}
int main(){

CASE(0)
	string flowers_[] = {"LLL",
 "PPP",
 "LLL"};
	  vector <string> flowers(flowers_, flowers_+sizeof(flowers_)/sizeof(*flowers_)); 
	int maxDiff = 1; 
	int _ = 7; 
END
CASE(1)
	string flowers_[] = {"LLL",
 "PPP",
 "LLL"};
	  vector <string> flowers(flowers_, flowers_+sizeof(flowers_)/sizeof(*flowers_)); 
	int maxDiff = 0; 
	int _ = 6; 
END
CASE(2)
	string flowers_[] = {"...",
 "...",
 "..."};
	  vector <string> flowers(flowers_, flowers_+sizeof(flowers_)/sizeof(*flowers_)); 
	int maxDiff = 3; 
	int _ = 0; 
END
CASE(3)
	string flowers_[] = {"LLPL.LPP",
 "PLPPPPLL",
 "L.P.PLLL",
 "LPL.PP.L",
 ".LLL.P.L",
 "PPLP..PL"};
	  vector <string> flowers(flowers_, flowers_+sizeof(flowers_)/sizeof(*flowers_)); 
	int maxDiff = 2; 
	int _ = 38; 
END
CASE(4)
	string flowers_[] = {"LLLLLLLLLL",
 "LLLLLLLLLL",
 "LLLLLLLLLL",
 "LLLLLLLLLL",
 "LLLLLLLLLL"};
	  vector <string> flowers(flowers_, flowers_+sizeof(flowers_)/sizeof(*flowers_)); 
	int maxDiff = 0; 
	int _ = -1; 
END
CASE(5)
	string flowers_[] = {"LLLP..LLP.PLL.LL..LP",
 "L.PL.L.LLLL.LPLLPLP.",
 "PLL.LL.LLL..PL...L..",
 ".LPPP.PPPLLLLPLP..PP",
 "LP.P.PPL.L...P.L.LLL",
 "L..LPLPP.PP...PPPL..",
 "PP.PLLL.LL...LP..LP.",
 "PL...P.PPPL..PLP.L..",
 "P.PPPLPLP.LL.L.LLLPL",
 "PLLPLLP.LLL.P..P.LPL",
 "..LLLPLPPPLP.P.LP.LL",
 "..LP..L..LLPPP.LL.LP",
 "LPLL.PLLPPLP...LL..P",
 "LL.....PLL.PLL.P....",
 "LLL...LPPPPL.PL...PP",
 ".PLPLLLLP.LPP...L...",
 "LL...L.LL.LLLPLPPPP.",
 "PLPLLLL..LP.LLPLLLL.",
 "PP.PLL..L..LLLPPL..P",
 ".LLPL.P.PP.P.L.PLPLL"};
	  vector <string> flowers(flowers_, flowers_+sizeof(flowers_)/sizeof(*flowers_)); 
	int maxDiff = 9; 
	int _ = 208; 
END
CASE(6)
string flowers_[] = {"L","P"};
	  vector <string> flowers(flowers_, flowers_+sizeof(flowers_)/sizeof(*flowers_)); 
	int maxDiff = 0; 
	int _ = 2; 
END
CASE(7)
	string flowers_[] = {"LLLP..LLP.PLL.LL..LPPLL.LL..LP",
 "L.PL.L.LLLL.LPLLPLP.PLL.LL..LP",
 "PLL.LL.LLL..PL...L..PLL.LL..LP",
 ".LPPP.PPPLLLLPLP..PPPLL.LL..LP",
 "LP.P.PPL.L...P.L.LLLPLL.LL..LP",
 "L..LPLPP.PP...PPPL..PLL.LL..LP",
 "PP.PLLL.LL...LP..LP.PLL.LL..LP",
 "PL...P.PPPL..PLP.L..PLL.LL..LP",
 "P.PPPLPLP.LL.L.LLLPLPLL.LL..LP",
 "PLLPLLP.LLL.P..P.LPLPLL.LL..LP",
 "..LLLPLPPPLP.P.LP.LLPLL.LL..LP",
 "..LP..L..LLPPP.LL.LPPLL.LL..LP",
 "LPLL.PLLPPLP...LL..PPLL.LL..LP",
 ".LPPP.PPPLLLLPLP..PPPLL.LL..LP",
 "LP.P.PPL.L...P.L.LLLPLL.LL..LP",
 "L..LPLPP.PP...PPPL..PLL.LL..LP",
 "PP.PLLL.LL...LP..LP.PLL.LL..LP",
 "PL...P.PPPL..PLP.L..PLL.LL..LP",
 "P.PPPLPLP.LL.L.LLLPLPLL.LL..LP",
 "PLLPLLP.LLL.P..P.LPLPLL.LL..LP",
 "..LLLPLPPPLP.P.LP.LLPLL.LL..LP",
 "..LP..L..LLPPP.LL.LPPLL.LL..LP",
 "LPLL.PLLPPLP...LL..PPLL.LL..LP",
 "LL.....PLL.PLL.P....PLL.LL..LP",
 "LLL...LPPPPL.PL...PPPLL.LL..LP",
 ".PLPLLLLP.LPP...L...PLL.LL..LP",
 "LL...L.LL.LLLPLPPPP.PLL.LL..LP",
 "PLPLLLL..LP.LLPLLLL.PLL.LL..LP",
 "PP.PLL..L..LLLPPL..PPLL.LL..LP",
 ".LLPL.P.PP.P.L.PLPLLPLL.LL..LP"};
	  vector <string> flowers(flowers_, flowers_+sizeof(flowers_)/sizeof(*flowers_)); 
	int maxDiff = 0; 
	int _ = -1; 
END
}
// END CUT HERE