abdelrahman_orief

Untitled

Sep 13th, 2020
863
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.  
  17. void solve(bitset<3005>b, int sze, int index, int sum)
  18. {
  19.     for (int i=0;i<d;i++)
  20.     {
  21.         if (b[index+i]==0 && index+i<n)
  22.         {
  23.             sum+=arr[index+i];
  24.         }
  25.         b[index+i]=1;
  26.     }
  27.     sze++;
  28.     if (sze==k)
  29.     {
  30.         maxi = max(sum, maxi);
  31.         return;
  32.     }
  33.     for (int i=index+1;i<n;i++)
  34.     {
  35.         solve(b, sze, i, sum);
  36.     }
  37. }
  38.  
  39.  
  40. int32_t main()
  41. {
  42.     //ios_base::sync_with_stdio(false);
  43.     //cin.tie(0);
  44.  
  45.  
  46.     int t, st;
  47.     cin>>t>>st;
  48.  
  49.     while (t--)
  50.     {
  51.  
  52.         cin>>n>>k>>d;
  53.         for (int i=0;i<n;i++)
  54.             cin>>arr[i];
  55.  
  56.         int maxBuilding = min(n, k*d);
  57.         if (st==2)
  58.         {
  59.             int psum[n];
  60.             for (int i=0;i<n;i++)
  61.             {
  62.                 if (i==0)
  63.                     psum[i] = arr[i];
  64.                 else
  65.                 {
  66.                     psum[i] = psum[i-1]+arr[i];
  67.                     if (i>=d)
  68.                         psum[i] -= arr[i-d];
  69.                 }
  70.             }
  71.             sort(psum, psum+n, greater<int>());
  72.             cout<<psum[0]<<endl;
  73.             continue;
  74.         }
  75.         if (st==3)
  76.         {
  77.             sort(arr, arr+n, greater<int>());
  78.             int finale=0;
  79.             for (int i=0;i<maxBuilding;i++)
  80.             {
  81.                 finale+=arr[i];
  82.             }
  83.             cout<<finale<<endl;
  84.             continue;
  85.         }
  86.         if (st==4)
  87.         {
  88.             cout<<maxBuilding<<endl;
  89.             continue;
  90.         }
  91.         bitset<3005> b;
  92.         for (int i=0;i<n;i++)
  93.             solve(b, 0, i, 0);
  94.         cout<<maxi<<endl;
  95.         maxi=0;
  96.     }
  97.  
  98.  
  99.  
  100. }
  101. /*
  102. 1 1
  103. 5 2 2
  104. 1 2 3 4 5
  105. */
  106.  
RAW Paste Data