Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <algorithm>
- #include <queue>
- #include <map>
- #include <set>
- #include <bitset>
- using namespace std;
- typedef long long ll;
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- ll n, k;
- cin >> n >> k;
- vector<vector<pair<ll, int>>> dp(n, vector<pair<ll, int>>(k, {0, 0}));
- vector<ll> a(n);
- for(int i = 0; i < n; ++i){
- cin >> a[i];
- }
- dp[0][0].first = a[0];
- for(int i = 1; i < n; ++i){
- dp[i][0].first = min(dp[i - 1][0].first, a[i]);
- dp[i][0].second = -1;
- }
- for(int i = 0; i < n; ++i){
- for(int j = 1; j < k; ++j){
- ll c = a[i];
- for(int v = 0; v < i; ++v){
- c = min(c, a[i - v]);
- if(dp[i - v - 1][j - 1].first + c >= dp[i][j].first){
- dp[i][j].first = max(dp[i - v - 1][j - 1].first + c, dp[i][j].first);
- dp[i][j].second = i - v - 1;
- }
- }
- }
- }
- cout << dp[n - 1][k - 1].first << "\n";
- int i = n - 1;
- int j = k - 1;
- vector<int> res;
- for(int x = 0; x < k - 1; ++x){
- res.push_back(dp[i][j - x].second + 1);
- i = dp[i][j - x].second;
- }
- for(int i = res.size() - 1; i > -1; --i){
- cout << res[i] << " ";
- }
- cout << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement