maximum rect solution

soruce.cpp

#define TIMETEST 0

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#if (TIMETEST)
#include <chrono>//for time check
#endif

using namespace std;

struct fNode
{
	bool isF;
	int width;
	fNode()
	{
		isF=false;
		width=0;
	}
};
struct fPos
{
	int x;
	int y;
	fPos(int _x,int _y)
	{
		x=_x;
		y=_y;
	}
};

vector< vector<fNode> > tMap;
vector<fPos> fsVector;

int main()
{
#if (TIMETEST)
	std::chrono::duration<double> sec;
#endif
	std::ios::sync_with_stdio(false);
#if (TIMETEST)
	std::chrono::system_clock::time_point start = std::chrono::system_clock::now();
#endif
	int n = 0;
	cin>>n;//testcase <=500
	for(int i=0; i<n; i++)
	{
		int w=0,h=0;//maximum 50x50
		int mSize=0;

		//map setting
		cin>>h>>w;
		tMap.assign(h,vector<fNode>(w,fNode()));
		for(int j=0; j<h; j++)
		{
			int count=0;
			while(count!=w)
			{
				int num;
				char c;
				cin>>num>>c;
				if(c=='f')
				{
					if(mSize<num)
						mSize=num;
					int wNum=num;
					for(int k=count;k<count+num;k++)		
					{
						tMap[j][k].isF=true;
						tMap[j][k].width=wNum;
						wNum--;

						fsVector.push_back(fPos(j,k));
					}
				}
				else
				{
					for(int k=count;k<count+num;k++)
					{
						tMap[j][k].isF=false;
					}
				}
				count+=num;
			}
		}

		//map check
		/*
		for(int j=0; j<h; j++)
		{
			for(int k=0;k<w;k++)
			{
				cout<<tMap[j][k].isF<<" ";
			}
			cout<<endl;
		}
		*/


		//make result
		for(int j=0;j<fsVector.size();j++)
		{
			int resWidth = tMap[fsVector[j].x][fsVector[j].y].width;
			int resHeight = 1;

			int k=1;
			while(1)
			{
				if(fsVector[j].x+k>=h || tMap[fsVector[j].x+k][fsVector[j].y].isF==false)
					break;
				if(tMap[fsVector[j].x+k][fsVector[j].y].width < resWidth)
				{
					if(mSize<resWidth*resHeight)
						mSize = resWidth*resHeight;
					resWidth = tMap[fsVector[j].x+k][fsVector[j].y].width;
					resHeight++;
				}
				else
					resHeight++;
				k++;
			}
			if(mSize<resWidth*resHeight)
				mSize = resWidth*resHeight;
		}

		//print max size of rect
		cout<<mSize<<endl;

		fsVector.clear();
		tMap.clear();
	}
#if (TIMETEST)
	sec = std::chrono::system_clock::now() - start;
	cout<<"time : "<<sec.count()<<"secs"<<endl;
#endif
	return 0;
}

input
1
16 12
12 e
2 e 6 f 4 e
6 e 1 f 5 e
1 e 3 f 2 e 2 f 3 e 1 f
2 e 6 f 3 e 1 f
3 e 5 f 2 e 2 f
4 e 3 f 5 e
3 e 3 f 6 e
2 e 6 f 4 e
3 e 4 f 5 e
4 e 1 f 4 e 2 f 1 e
2 e 3 f 4 e 2 f 1 e
1 e 3 f 4 e 2 f 2 e
2 f 5 e 2 f 3 e
12 e
12 e