問題
http://community.topcoder.com/stat?c=problem_statement&pm=11855&rd=14731
解き方
９０００以上となる数をすべて保存しては間に合わないので、
その始点と終点のみ保存してあげて、その間の範囲を計算していくことで
メモリ、計算量ともに制限内で解くことができる。
コード
pair<int,int> p[1000000];
class Over9000Rocks {
public: int countPossibilities(vector<int> lowerBound, vector<int> upperBound) {
int n=lowerBound.size();
int m=0;
for(int mask=1;mask<(1<<n);mask++){
int minx=0,maxx=0;
FORE(i,0,n)if(mask&(1<<i)){
minx+=lowerBound[i];
maxx+=upperBound[i];
}
minx=max(minx,9001);
if(minx<=maxx){
p[m++]=make_pair(minx,1);
p[m++]=make_pair(maxx+1,-1);
}
}
sort(p,p+m);
int ret=0,cur=0;
FORE(i,0,m){
cur+=p[i].second;
if(cur!=0)ret+=p[i+1].first-p[i].first;
}
return ret;
}
};
class Over9000Rocks {
public: int countPossibilities(vector<int> lowerBound, vector<int> upperBound) {
int n=lowerBound.size();
int m=0;
for(int mask=1;mask<(1<<n);mask++){
int minx=0,maxx=0;
FORE(i,0,n)if(mask&(1<<i)){
minx+=lowerBound[i];
maxx+=upperBound[i];
}
minx=max(minx,9001);
if(minx<=maxx){
p[m++]=make_pair(minx,1);
p[m++]=make_pair(maxx+1,-1);
}
}
sort(p,p+m);
int ret=0,cur=0;
FORE(i,0,m){
cur+=p[i].second;
if(cur!=0)ret+=p[i+1].first-p[i].first;
}
return ret;
}
};