Cod sursa(job #2764937)

Utilizator DragosC1Ciobanu Dragos DragosC1 Data 23 iulie 2021 17:57:36
Problema Ferma Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <fstream>
using namespace std;

int n, k;
int a[10001];
int Max = 0; // consideram ca rezultatul nu poate fi mai mic de 0 (scrie in enunt)
int dp[1001][10001];
int sum[10001];

void read() {
    int i;
    ifstream f("ferma.in");
    f >> n >> k;
    for (i = 1; i <= n; i++)
        f >> a[i];
    f.close();
}

void solve() {
    int val, i, j;

    // sume partiale pe vectorul a
    for (i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + a[i];

    // fara circularitate
    // Formula : dp[i][j] = max(dp[i][j - 1], dp[i - 1][nr] - sum[nr] + sum[j]) -> o tratam inteligent in O(k * n) nu O(k * n^2)
    for (i = 1; i <= k; i++) {
        val = dp[i - 1][i - 1] - sum[i - 1];
        for (j = i; j <= n; j++) {
            dp[i][j] = max(dp[i][j - 1], val + sum[j]);
            val = max(val, dp[i - 1][j] - sum[j]);
        }
    }
    Max = max(Max, dp[k][n]);

    // tratam circularitatea
    // pentru k = 1 -> tratam cazul in care consideram suma primelor i numere sau nu
    for (i = 1; i <= n; i++)
        dp[1][i] = max(dp[1][i - 1], sum[i]);
    
    // pentru celelalte cazuri fortam ca secventa sa contina si a[1] daca se poate (pentru circularitate)
    for (i = 2; i <= k; i++) {
        dp[i][1] = a[1];
        val = 0;
        for (j = 2; j <= n; j++) {
            dp[i][j] = max(dp[i][j - 1], val + sum[j]);
            val = max(val, dp[i - 1][j] - sum[j]);
        }
    }

    // in final comparam rezultatul in care putem avea circularitate cu cel fara de mai devreme
    for (i = k; i <= n; i++)
        Max = max(Max, dp[k][i] + sum[n] - sum[i]);   // consideram si cazul in care ultima secventa se lipeste de rezultatul fara circularitate
}

void output() {
    ofstream g("ferma.out");
    g << Max;
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}