fork download
copy 
  1.  
  2.     #include <bits/stdc++.h>
  3.  
  4.     using namespace std;
  5.  
  6.     using ll = long long;
  7.     const int MOD = 1000000007; 
  8.     const int MOD2 =  998244353; 
  9.     const ll INF = 1e18;
  10.     const ll NEGINF = -1e18;
  11.     const int MX = 1000001; //check the limits, dummy
  12.  
  13.  
  14.     ll modExp(ll base, ll power) {
  15.         if (power == 0) {
  16.             return 1;
  17.         } else {
  18.             ll cur = modExp(base, power / 2); cur = cur * cur; cur = cur % MOD;
  19.             if (power % 2 == 1) cur = cur * base;
  20.             cur = cur % MOD;
  21.             return cur;
  22.         }
  23.     }
  24.  
  25.     ll inv(ll base) {
  26.         return modExp(base, MOD-2);
  27.     }
  28.  
  29.  
  30.     ll mul(ll A, ll B) {
  31.         return (A*B)%MOD;
  32.     }
  33.  
  34.     ll add(ll A, ll B) {
  35.         return (A+B)%MOD;
  36.     }
  37.  
  38.     ll dvd(ll A, ll B) {
  39.         return mul(A, inv(B));
  40.     }
  41.  
  42.     ll sub(ll A, ll B) {
  43.         return (A-B+MOD)%MOD;
  44.     }
  45.     ll cielDiv(ll A , ll B) {
  46.         return (A + B - 1)/B;
  47.     } 
  48.  
  49.     ll* facs = new ll[MX];
  50.     ll* facInvs = new ll[MX];
  51.  
  52.     ll choose(ll a, ll b) {
  53.         if (b > a) return 0;
  54.         if (a < 0) return 0;
  55.         if (b < 0) return 0;
  56.         ll cur = facs[a];
  57.         cur = mul(cur, facInvs[b]);
  58.         cur = mul(cur, facInvs[a-b]);
  59.         return cur;
  60.     }
  61.  
  62.  
  63.  
  64.  
  65.     void initFacs() {
  66.         facs[0] = 1; 
  67.         facInvs[0] = 1;
  68.         for (int i = 1 ; i < MX ; i ++ ) {
  69.             facs[i] = (facs[i-1] * i) % MOD;
  70.             facInvs[i] = inv(facs[i]);
  71.         }
  72.     }
  73.     ll dp[201][201];
  74.     int main()  {
  75.         ios_base::sync_with_stdio(0); cin.tie(0);  
  76.         int n,k,x ;cin >> n >> k >> x ;
  77.        vector<ll> arr(n);
  78.         for (int i = 0 ; i < n; i ++) {
  79.             cin >> arr[i]; 
  80.         }
  81.         memset(dp , -1, sizeof(dp)); 
  82.         dp[0][0] = 0;
  83.         for (int i = 0 ; i <= n; i ++) {
  84.             ll v = arr[i]; 
  85.             for (int j = 1 ; j <= x; j ++) {
  86.                 for (int currk = 1 ; currk <= k && (i - currk) >= 0; currk ++) {
  87.                     dp[i + 1][j] =  max(dp[i][j], dp[i - currk][j - 1] + v); 
  88.                 } 
  89.             }
  90.         }
  91.         ll res = -1;
  92.         for (int i = 0 ; i <= n;  i++) {
  93.             res = max(res , dp[i][x]); 
  94.         }
  95.  
  96.         cout << res << endl; 
  97.         return 0;
  98.  
  99.     }
  100.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5 2 3
5 1 3 10 1
stdout
copy 
9
https://ideone.com/haJRb7
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!