AOJ 1297 : Swimming Jam

問題リンク：Swimming Jam | Aizu Online Judge

問題概要：
n人の人が２つのレーンを使って水泳をする
入力として人の数nとそれぞれの人が１レーンを泳ぐのにかかる時間と往復する回数が与えられる
ある人が泳いでる途中で前の人に追いついてしまった場合はレーンの端に到達するまでずっと後ろをついていく
レーンの端に到達したらその人を抜いていく
決められた回数を往復し終わった人はプールからあがる
全ての人が決められた回数往復し終わるまでにかかる時間を計算せよ

解法：
まず泳ぐのが遅い順番にソートする
追いつく可能性があるのは自分より遅い人なのでソートして自分より前にいる人だけをチェックすれば良い
n人の人をそれぞれ遅い順番にシュミレートしていく
１レーンを泳ぐ間に自分より遅い人が同じ時間帯で同じレーンを泳いでいないかを確認し、その様な人が存在する場合はそのレーンを泳ぎ終わる時間をその人が終わる時間と同じにする
いない場合は予定通りの時間とする
泳いでいる人の情報は以下の様なstructを定義して管理した

struct P
{
    pair<int,int> time;
    bool dir;
};

このstructはtime.firstからtime.secondまでの間、方向dir(１レーンを泳いでいるのか２レーンを泳いでいるのか)を泳いでいる亊を意味する

コード：

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define all(n) (n).begin(),(n).end()
#define inf (1<<29)

using namespace std;
typedef pair<int,int> ii;

struct P
{
  ii time;
  bool dir;//0->上, 1->下
  P(ii time=ii(inf,inf),bool dir=false):time(time),dir(dir){}
};

int ans;
int n;

void compute(vector<vector<P> > &record,ii person)
{
  int cur = 0;
  record.push_back(vector<P>());


  rep(i,person.second*2)
    {
      bool dir = i % 2;//0->上,1->下
      int next = cur + person.first;

      rep(j,record.size()-1)
	{
	  rep(k,record[j].size())
	    {
	      P p = record[j][k];
	      if(p.dir != dir)continue;
	      if(p.time.first > cur)break;

	      if(p.time.second == next || p.time.first == cur)
		{
		  break;		  
		}
	      else if(p.time.first < next && next < p.time.second)
		{
		  next = max(p.time.second,next);
		  break;
		}
	    }
	}

      record[record.size()-1].push_back(P(ii(cur,next),dir));
      cur = next;
      ans = max(ans,next);
    } 
}

int main()
{
  while(scanf("%d",&n),n)
    {
      ans = 0;
      vector<ii> info(n);
      rep(i,n)scanf("%d %d",&info[i].first,&info[i].second);
      sort(all(info),greater<ii>());

      vector<vector<P> > record;

      rep(i,n)compute(record,info[i]);

      printf("%d\n",ans);

    }
  return 0;
}