Submission #884387

#	Time	Username	Problem	Language	Result	Execution time	Memory
884387		Asamai	Feast (NOI19_feast)	C++17	71 / 100	1032 ms	15956 KiB

feast

#include <bits/stdc++.h>

using namespace std;

template<class A, class B> bool maximize(A& x, B y) {if (x < y) return x = y, true; else return false;}
template<class A, class B> bool minimize(A& x, B y) {if (x > y) return x = y, true; else return false;}

#define     all(a)                a.begin(), a.end()
#define     pb                    push_back
#define     pf                    push_front
#define     fi                    first
#define     se                    second
#define     int                   long long

typedef     long long             ll;
typedef     unsigned long long    ull;
typedef     double                db;
typedef     long double           ld;
typedef     pair<db, db>          pdb;
typedef     pair<ld, ld>          pld;
typedef     pair<int, int>        pii;
typedef     pair<ll, ll>          pll;
typedef     pair<ll, int>         plli;
typedef     pair<int, ll>         pill;

const int MAX_N = 3e5 + 5;
const int mod = 1e9 + 7;
const ll inf = 1e18;

int n, k;
int a[MAX_N];
int pref[MAX_N];
int cntAm;
int dp[2][MAX_N][2];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    if (fopen("party.inp", "r")) {
        freopen("party.inp", "r", stdin);
        freopen("party.out", "w", stdout);
    }

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pref[i] = pref[i - 1] + a[i];
        cntAm += (a[i] < 0);
    }

    if (cntAm == 0) {
        cout << pref[n];
        return 0;
    }

    if (k == 1) {
        int ans = 0;
        int prefMin = 0;
        for (int i = 1; i <= n; i++) {
            maximize(ans, pref[i] - prefMin);
            minimize(prefMin, pref[i]);
        }
        cout << ans;
        return 0;
    }

    if (cntAm == 1) {
        // k > 1
        for (int i = 1; i <= n; i++) {
            if (a[i] < 0) {
                cout << pref[n] - a[i];
                return 0;
            }
        }
        return 0;
    }

    bool curr = 0, nxt = 1;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= 1; j++) {
            dp[curr][i][j] = dp[nxt][i][j] = -inf;
        }
    }
    dp[curr][0][0] = 0;

    for (int i = 0; i < n; i++, swap(curr, nxt)) {
        for (int j = 0; j <= i; j++) {
            if (dp[curr][j][0] > -inf) {
                // dp[curr][j][0]
                maximize(dp[nxt][j][0], dp[curr][j][0]); // khong mo
                maximize(dp[nxt][j + 1][1], dp[curr][j][0] + a[i + 1]); // mo
            }

            if (dp[curr][j][1] > -inf) {
                // dp[curr][j][1]
                maximize(dp[nxt][j][1], dp[curr][j][1] + a[i + 1]); // tiep tuc
                maximize(dp[nxt][j][0], dp[curr][j][1]); // dong lai
            }
        }

        for (int j = 0; j <= i; j++) {
            for (int state = 0; state <= 1; state++) {
                dp[curr][j][state] = -inf;
            }
        }
    }

    int ans = 0;
    for (int j = 0; j <= k; j++) {
        for (int state = 0; state <= 1; state++) {
            maximize(ans, dp[curr][j][state]);
        }
    }

    cout << ans;

    return 0;
}

/*

dp[i][j][0/1]

Thursday, 07 December 2023
15:25:54
*/

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen("party.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen("party.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 0 / 29