Cod sursa(job #2192646)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 6 aprilie 2018 19:34:55
Problema Ferma Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<ld, ld>
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

const int kMaxN = 10005;
const int kMaxK = 1005;
const int kInf = (1 << 30) - 1;

int n, k;
int a[kMaxN];
int s[kMaxN];
int dp[kMaxK][kMaxN];

void BuildDp(int start) {
  for (int i = 0; i < kMaxK; i++) {
    for (int j = 0; j < kMaxN; j++) {
      dp[i][j] = -kInf;
    }
  }

  for (int i = 0; i <= n; i++) {
    dp[0][i] = 0;
  }
  for (int i = 1; i <= k; i++) {
    int maxi = dp[i - 1][start - 1];
    for (int j = start; j <= n; j++) {
      dp[i][j] = max(dp[i][j - 1], s[j] + maxi);
      maxi = max(maxi, dp[i - 1][j] - s[j]);
    }
  }
}

int main() {
  cin.sync_with_stdio(false);

  ifstream cin("ferma.in");
  ofstream cout("ferma.out");

  cin >> n >> k;

  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    s[i] = s[i - 1] + a[i];
  }

  int ans = 0;

  BuildDp(1);
  for (int i = 1; i <= n; i++) {
    ans = max(ans, dp[k][i]);
  }

  BuildDp(2);
  for (int i = 2; i <= n; i++) {
    ans = max(ans, a[1] + dp[k - 1][i] + s[n] - s[i]);
  }

  cout << ans << '\n';

  return 0;
}