SRM 580 Div1 Easy EelAndRabbit

問題

うなぎが複数匹おり、i番目のうなぎは狐の眼前をt[i]秒からt[i] + l[i]秒にかけて通過していく。狐は2回うなぎを獲ろうとし、1回の試行で眼前を通過しているうなぎを好きなだけ獲得できる。最大獲得数を求めよ。

やりかた

調べるべきポイントは各うなぎの頭が眼前に来た時と、しっぽが眼前を過ぎていく時点である。うなぎがN匹いれば2*Nポイントから2ポイント選んでその時の獲得数を調べる。これを全ての2ポイントの組み合わせについて調べて最大数を求める。

以下ソース。

class EelAndRabbit {
public:
  int getmax(vector <int> l, vector <int> t) {
    int result = 0;
    int N = l.size();
    vector<int> p;
    for(int i = 0; i < N; i++){
      p.push_back(t[i]);
      p.push_back(t[i] + l[i]);
    }
    
    
    for(int i = 0; i < 2 * N; i++){
      for(int j = 0; j < 2 * N; j++){
	int cnt = 0;
	vector<bool> used(N, false);
	
	for(int k = 0; k < N; k++){
	  if(t[k] <= p[i] && p[i] <= t[k] + l[k] && !used[k]){
	    used[k] = true;
	    cnt++;
	  }
	}
	for(int k = 0; k < N; k++){
	  if(t[k] <= p[j] && p[j] <= t[k] + l[k] && !used[k]){
	    used[k] = true;
	    cnt++;
	  }
	}
	result = max(result, cnt);
      }
    }
    return result;
  }
};