SRM387 div1 medium

動物的直感でAC。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>

using namespace std;

class IntervalSubsets 
{
	public:

		int n;
		int cache[55];
		vector<pair<int,int> > interval;

		int rec(int p)
		{
			int &r=cache[p];
			if(r!=-1)
				return r;
			else
			{
				r=0;
				int ss=interval[p].second+1,se;
				for(int i=0;i<n;i++)
					if(ss<=interval[i].first)
					{
						se=interval[i].second;
						break;
					}
				for(int i=0;i<n;i++)
					if(ss<=interval[i].first && interval[i].first<=se)
					{
						r+=rec(i);
						se=min(se,interval[i].second);
					}
				return (r!=0)?r:r=1;
			}
		}	

		int numberOfSubsets(vector <int> start, vector <int> finish) 
		{
			interval.clear();
			start.push_back(0);
			finish.push_back(0);
			n=start.size();
			for(int i=0;i<n;i++)
				interval.push_back(make_pair(start[i],finish[i]));
			sort(interval.begin(),interval.end());

			memset(cache,-1,sizeof(cache));
			return rec(0);
		}
};