Submission #1414799

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;

int main() {
  int n,m;
  cin >> n >> m;
  vector<int> v[111111];
  for(int i=0; i<n; i++) {
    int x,y;
    cin >> x >> y;
    v[x].push_back(x+y);
  }
  int d[111111];
  fill(d,d+111111,-(1<<30));
  d[0]=0;
  priority_queue<P> que;
  que.push(P(0,0));
  while(!que.empty()) {
    P p=que.top();que.pop();
    int x=p.second,c=p.first;
    if(m<x||d[x]>c) continue;
    if(d[x+1]<c) {
      d[x+1]=c;
      que.push(P(c,x+1));
    }
    if(x&&d[x-1]<c-2) {
      d[x-1]=c-2;
      que.push(P(c-2,x-1));
    }
    for(int i=0; i<v[x].size(); i++) {
      int y=v[x][i],cc=y-x+c;
      if(d[y]<cc) {
        d[y]=cc;
        que.push(P(cc,y));
      }
    } 
  }
  cout << d[m] << endl;
  return 0;
}

Submission Info

Judge Result