Cod sursa(job #1855350)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 23 ianuarie 2017 16:32:06
Problema Ferma Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <fstream>

using namespace std;

const int KMAX = 1000 + 5;
const int NMAX = 10000 + 5;
const int INF = 2E9 + 15;

int N;
int v[NMAX];

int dp1[KMAX][NMAX]; //dp1[i][j] = daca iau i subsecvente si ultima se termina pe pozitia j
int dp2[KMAX][NMAX]; //dp2[i][j] = daca iau i subsecvente si ultima se termina pe o pozitie <= j

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

    int K = 0;
    cin >> N >> K;

    for (int i = 1; i <= N; ++ i)
        cin >> v[i];

    for (int j = 1; j <= N; ++ j)
        dp1[0][j] = -INF;
    for (int i = 1; i <= K; ++ i)
        dp1[i][0] = dp2[i][0] = -INF;

    for (int i = 1; i <= K; ++ i) {
        for (int j = 1; j <= N; ++ j) {
            if (j >= 2)
                dp1[i][j] = v[j] + max(dp1[i][j - 1], dp2[i - 1][j - 2]);
            else
                dp1[i][j] = v[j] + dp1[i][j - 1];

            dp2[i][j] = max(dp2[i][j - 1], dp1[i][j]);

            if (dp1[i][j] < -INF / 2)
                dp1[i][j] = -INF;
            if (dp2[i][j] < -INF / 2)
                dp2[i][j] = -INF;
        }
    }

    int ans = dp2[K][N];

    //Force first element to be taken
    /*for (int j = 1; j <= N; ++ j)
        dp1[0][j] = -INF;
    for (int i = 1; i <= K; ++ i)
        dp1[i][0] = dp2[i][0] = -INF;

    for (int i = 0; i <= K; ++ i)
        dp1[i][1] = dp2[i][1] = -INF;
    dp1[1][1] = dp2[1][1] = v[1];

    for (int i = 1; i <= K; ++ i) {
        for (int j = 2; j <= N; ++ j) {
            if (j >= 2)
                dp1[i][j] = v[j] + max(dp1[i][j - 1], dp2[i - 1][j - 2]);
            else
                dp1[i][j] = v[j] + dp1[i][j - 1];

            dp2[i][j] = max(dp2[i][j - 1], dp1[i][j]);

            if (dp1[i][j] < -INF / 2)
                dp1[i][j] = -INF;
            if (dp2[i][j] < -INF / 2)
                dp2[i][j] = -INF;
        }
    }

    //Tackle circularity
    int sum = 0;
    for (int i = N; i > 0; -- i) {
        sum += v[i];

        if (dp2[K][i - 1] != -INF)
            ans = max(ans, dp2[K][i - 1] + sum);
    }*/

    //Print
    if (ans < 0)
        cout << "0\n";
    else
        cout << ans << '\n';
    return 0;
}