Problem C - Hot Dog Proliferation

問題

数列 V_i(≧0) の値が部分的に与えられる．（与えられない部分は 0 としてよい）．このうち， 2≧V_i となる部分について
(V_i-1，V_i，V_i+1)←(V_i-1＋1，V_i−2，V_i+1＋1)
という処理を繰り返し，全体が 0≦V_i≦1 となるようにする．この処理は最低何回行う必要があるか？

Small だけ

いくつか手で試していれば，特に処理の順序には関係ないことが分かるはず．
なので単純にシミュレートするのが楽．Largeだと時間とメモリに無理が出る．16TBとか必要になる．

#include <iostream>
#include <map>
using namespace std;
typedef pair<int, int> Vender;

int solve()
{
  int C;
  map<int,int> vender;
  cin >> C;
  for( int i = 0 ; i < C ; ++i ) {
    int P, V;
    cin >> P >> V;
    vender.insert(Vender(P, V));
  }

  int cnt = 0;
  for( bool cont = true ; cont ; ) {
    cont = false;
    map<int,int>::iterator it;
    for( it = vender.begin() ; it != vender.end() ; ++it ) {
      if( it->second == 1 ) continue;
      cont = true;
      ++cnt;
      int p = it->first, v = it->second;
      if( vender.find(p-1) != vender.end() ) vender[p-1]++;
      else vender.insert(Vender(p-1,1));
      if( vender.find(p+1) != vender.end() ) vender[p+1]++;
      else vender.insert(Vender(p+1,1));
      if( (vender[p] -= 2) == 0 ) vender.erase(it);
    }
  }
  return cnt;
}

int main(void)
{
  int T;
  cin >> T;
  for( int t = 1 ; t <= T ; ++t ) {
    cerr << "Case #" << t << "\n";
    cout << "Case #" << t << ": " << solve() << "\n";
  }
  return 0;
}