Advertisement
Guest User

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.  
Advertisement
RAW Paste Data Copied
Advertisement