fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. ll dp[300005][3];
  8. int c[300005][3];
  9. vector<int> a;
  10. vector<int> b;
  11. int cnt;
  12.  
  13. ll solve(int idx, ll val) {
  14. cout<<idx<<" "<<val<<endl;
  15. if (idx == a.size() - 1) return 0;
  16. if (val - a[idx] > 2) return 1LL << 60;
  17. if (c[idx][val - a[idx]] == cnt) return dp[idx][val - a[idx]];
  18.  
  19. dp[idx][val - a[idx]] = cnt;
  20.  
  21. if (val == a[idx + 1]) {
  22. return dp[idx][val - a[idx]] = min(solve(idx + 1, a[idx+1]) + b[idx], solve( idx + 1, a[idx+ 1] + 1) + b[idx + 1]);
  23. }
  24.  
  25. return dp[idx][val-a[idx]] = solve( idx + 1, a[idx + 1]);
  26. }
  27.  
  28. int main()
  29. {
  30. ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  31. int q; cin >> q;
  32. memset(dp, -1LL, sizeof(dp));
  33. while (q--)
  34. {
  35. int n; cin >> n;
  36. b.resize(n);
  37. a.resize(n);
  38. cnt++;
  39.  
  40. for (int i = 0; i < n; i++) {
  41. cin >> a[i] >> b[i];
  42. }
  43.  
  44. cout << solve(0, a[0]) << '\n';
  45.  
  46. }
  47.  
  48. return 0;
  49. }
  50.  
Success #stdin #stdout 0s 10612KB
stdin
3
3
2 4
2 1
3 5
3
2 3
2 10
2 6
4
1 7
3 3
2 6
1000000000 2
stdout
0 2
1 3
2 4
2 3
1 2
2 3
2
0 2
1 3
2 2
1 2
2 3
2 2
9
0 1
1 3
2 2
3 1000000000
0