fork download
  1. #include<iostream>
  2. #include<memory.h>
  3. #define MAXN 50001
  4. #define MAXP 20
  5. using namespace std;
  6.  
  7. int n;
  8. int dp[MAXN];
  9. int ST[MAXN][MAXP];
  10. int V[MAXN] , A[MAXN] , B[MAXN];
  11.  
  12. int getmax(int L , int R)
  13. {
  14. if(L > R)
  15. return 0;
  16. int s = 0;
  17. while((1 << (s + 1)) <= R - L + 1)
  18. s++;
  19. return max(ST[L][s] , ST[R - (1 << s) + 1][s]);
  20. }
  21.  
  22. void update(int w)
  23. {
  24. ST[w][0] = dp[w];
  25. for(int i = 1 ; w + (1 << i) - 1 <= n ; i++)
  26. ST[w][i] = max(ST[w][i - 1] , ST[w + (1 << (i - 1))][i - 1]);
  27. }
  28.  
  29. int main()
  30. {
  31. ios::sync_with_stdio(false);
  32. while(cin>>n)
  33. {
  34. memset(ST , 0 , sizeof(ST));
  35. for(int i = 1 ; i <= n ; i++)
  36. {
  37. cin>>V[i]>>A[i]>>B[i];
  38. A[i] = A[i] + i;
  39. B[i] = min(B[i] + i - 1 , n);
  40. }
  41. for(int i = n ; i >= 1 ; i--)
  42. {
  43. dp[i] = V[i] + getmax(A[i] , B[i]);
  44. update(i);
  45. }
  46. cout<<dp[1]<<endl;
  47. }
  48. return 0;
  49. }
  50.  
Success #stdin #stdout 0.02s 7716KB
stdin
3
1 1 2
2 2 3
3 3 4
3
1 1 3
2 2 4
3 3 5
4
10 3 10
7 1 7
5 2 5
1 1 2
5
1 1 9
10 3 10
7 1 7
5 2 5
1 1 2
stdout
3
4
11
13