590D - Top Secret Task - CodeForces Solution

#include <bits/stdc++.h>

#define se second
#define fi first
#define ll long long

#define mp make_pair
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)x.size()
#define pb push_back

#define MOD 1000000007

const int _mx16 = (1 << 16) - 1;
using namespace std;
void easy() {
   int n, k, s;
   cin >> n >> k >> s;
   vector<int> q(n);
   for (int &i : q) cin >> i;
   int mx_op = n * (n + 1) / 2;
   vector<vector<int>> dp(k + 1, vector<int>(mx_op + 1, 1e9));
   dp[0].assign(mx_op, 0);
   for (int i = 0; i < n; i++) {
      for (int j = min(i + 1, k); j >= 1; j--) {
         const int lb = i - j + 1;
         for (int z = (i + 1) * (i + 2) / 2; z >= lb; z--) {
            dp[j][z] = min(dp[j][z], dp[j - 1][z - lb] + q[i]);
         }
      }
   }
   s = min(s, mx_op);
   int ans = 1e9;
   for (int i = 0; i <= s; i++) {
      ans = min(ans, dp[k][i]);
   }
   cout << ans;
}

int main() {
   // freopen("vcl.in", "r", stdin);
   // freopen("vcl.out", "w", stdout);
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   easy();
}