# 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