abdelrahman_orief

Untitled

Sep 14th, 2020
549
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3. #define modulo 1000000007
  4. #define int long long
  5. #pragma GCC optimize("-Ofast")
  6. #define float double
  7. #define PI 3.141592653589793238462643383279502884
  8. #define sinDegrees(x) sin((x) * PI / 180.0)
  9. #define tanDegrees(x) tan((x) * PI / 180.0)
  10. #define atanDegrees(x) atan(x)* 180.0 / PI
  11.  
  12. using namespace std;
  13.  
  14. int arr[3005];
  15. int n, k, d, maxi=0;
  16. int dp[3005][3005];
  17.  
  18. int solve(int sze, int index, int sum)
  19. {
  20.     if (index>=n)
  21.         return sum;
  22.  
  23.     if (dp[sze+1][index])
  24.     {
  25.         return sum+dp[sze+1][index];
  26.     }
  27.  
  28.     int without = solve(sze, index+1, sum)-sum;
  29.  
  30.     int temp = sum;
  31.  
  32.     sze++;
  33.  
  34.     for (int i=index;i<min(index+d, n);i++)
  35.         sum+=arr[i];
  36.     if (sze==k)
  37.         return max(sum, without+temp);
  38.     int with = solve(sze, index+d, sum)-temp;
  39.  
  40.     dp[sze][index] = max(with, without);
  41.  
  42.     return max(with+temp, without+temp);
  43.  
  44.  
  45.  
  46. }
  47.  
  48.  
  49. int32_t main()
  50. {
  51.     //ios_base::sync_with_stdio(false);
  52.     //cin.tie(0);
  53.  
  54.  
  55.     int t, st;
  56.     cin>>t>>st;
  57.  
  58.     while (t--)
  59.     {
  60.  
  61.         cin>>n>>k>>d;
  62.         for (int i=0;i<n;i++)
  63.             cin>>arr[i];
  64.         cout<<solve(0, 0, 0)<<endl;
  65.         memset(dp, 0, sizeof(dp));
  66.     }
  67.  
  68.  
  69.  
  70.  
  71. }
  72. /*
  73. 1 1
  74. 5 2 2
  75. 1 2 3 4 5
  76. */
  77.  
RAW Paste Data