# Code

a guest
May 15th, 2022
66
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include<bits/stdc++.h>
2.
3. using namespace std;
4.
5. #define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
6. #define pb push_back
7. #define TIME cerr<<"Time Taken:"<<(float)clock()/CLOCKS_PER_SEC*1000<<"ms"<<endl
8.
9. typedef long long int lli;
10.
11.
12. lli dp[2001][4002];
13. lli suffixSum[2001];
14. // tt is the sum of a[i][0] of all bombs that will give us bad luck
15. // im simple tt is time we are left with.
16. // for the ith bomb we can explode it or keep it
17. // if keep it then tt=tt+a[i][0]
18. // if we destroy it then tt=tt-1 as it takes 1 sec to destroy a bomb
19. // if at any point tt>=n then we can explode all the bombs from i to n-1 (indexing starts from 0)
20. // hence returing suffixsum of a[i][1] at line 73
21. // thus tt>=-n && tt<=n hence dp will be of size n * (2n)
22. lli f(auto &a,lli i,lli tt)
23. {
24. lli n=a.size();
25. if(i==a.size())
26. {
27. if(tt>=0)
28. return 0;
29. return -1e18;
30. }
31. if(tt>=n)
32. return suffixSum[i];
33. lli &ans=dp[i][tt+n];
34. if(ans!=-1)
35. return ans;
36. lli x=f(a,i+1,tt+a[i][0]);
37. lli y=f(a,i+1,tt-1)+a[i][1];
38. if(y<0)
39. y=-1e18;
40. return ans=max(x,y);
41. }
42. int main() {
43. fastio();
44. #ifndef ONLINE_JUDGE
45. freopen("input.txt", "r", stdin);
46. freopen("output.txt", "w", stdout);
47. freopen("Error.txt", "w", stderr);
48. #endif
49. lli t=1,testcases=1;
50. cin>>t;
51. while(t>=testcases)
52. {
53. memset(dp,-1,sizeof(dp));
54. lli n;
55. cin>>n;
56. vector<vector<lli>> a(n,vector<lli>(2));
57. for(lli i=0;i<n;i++)
58. for(lli j=0;j<2;j++)
59. cin>>a[i][j];
60. suffixSum[n-1]=a[n-1][1];
61. for(lli i=n-2;i>=0;i--)
62. suffixSum[i]=suffixSum[i+1]+a[i][1];
63. cout<<f(a,0,0)<<endl;
64. //cout<<"Case #"<<testcases<<": "<<ans<<endl;
65. testcases++;
66. }
67. TIME;
68. return 0;
69. }
70.