Anonymous

#include <iostream>#include <algorithm>#include <queue>#include <vector>using namespace std;struct Node{  int dist, fuel, turns, avail;  bool operator<(const Node& b) const  { return dist > b.dist; }};istream& operator>>(istream& in, Node& n){ n.turns = 0; return in >> n.dist >> n.fuel; }int n;vector<Node> nodes;int dijkstra(){  priority_queue<Node*> q;  q.push(&nodes[n]);  while(!q.empty())  {  }  return -1;}int scan(){  int l = 0, r = 0;  for(int turns = 0; turns < n; ++turns)  {    int nl = n + 5, nr = -1;    for(int i = r; i >= l; --i)    {      //cout << i << endl;      int nnr = i + 1;      if(nodes[i].avail >= nodes[i].dist)        return turns;      while(nnr < n && nodes[i].dist - nodes[nnr].dist <= nodes[i].avail)      {        //printf("%d %d %d %d %d\n", nnr, nodes[nnr].dist, i, nodes[i].dist, nodes[i].avail);        int newVal = nodes[i].avail - (nodes[i].dist - nodes[nnr].dist)          + nodes[nnr].fuel; //TODO: max with previous if previous in same turn        if(nodes[nnr].turns == turns && newVal <= nodes[nnr].avail)          break;        nodes[nnr].turns = turns;        nodes[nnr].avail = newVal;        nr = max(nr, nnr);        nl = min(nl, nnr);        ++nnr;      }    }    //cout << nl << ", " << nr << endl;    if(nr == -1)      return -1;    r = nr; l = nl;  }  return -1;}int main(){  int S; cin >> S;  for(int s = 0; s < S; ++s)  {    cin >> n; ++n;    nodes.resize(n);    for(int i = 1; i < n; ++i)      cin >> nodes[i];    sort(nodes.begin() + 1, nodes.end());    cin >> nodes[0];    //Node start; cin >> start;    nodes[0].avail = nodes[0].fuel;    cout << scan() << endl;  }}