Submission #1270952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270952		quangminh412	Feast (NOI19_feast)	C++17	71 / 100	195 ms	327680 KiB

feast

/*
  Ben Watson

  Quang Minh MasterDDDDD
*/

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const string name = "test";

void solve();
signed main()
{
    if (fopen((name + ".inp").c_str(), "r"))
    {
        freopen((name + ".inp").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();

    return 0;
}

// main program
const int maxn = 3e5 + 1;

ll prefix[maxn];
int a[maxn];
int n, k;

void subtask1()
{
    cout << prefix[n] << '\n';
}

void subtask2()
{
    ll res = prefix[n];
    for (int i = 1; i <= n; i++)
        if (a[i] < 0)
            res -= a[i];
    cout << res << '\n';
}

void subtask3()
{
    ll mn = 0, res = 0;
    for (int i = 1; i <= n; i++)
    {
        res = max(res, prefix[i] - mn);
        mn = min(mn, prefix[i]);
    }
    cout << res << '\n';
}

void subtask456()
{
    vector<vector<ll>> dp(k + 1, vector<ll>(n + 1, 0)), f(k + 1, vector<ll>(n + 1, 0));
    ll res = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= k; j++)
        {
            dp[j][i] = max(dp[j][i - 1], f[j - 1][i - 1]) + a[i];
            f[j][i] = max(f[j][i - 1], dp[j][i]);
            res = max(res, dp[j][i]);
        }
    cout << res << '\n';
}

void solve()
{
    cin >> n >> k;
    int cnt = 0;
    bool issub1 = true;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] < 0)
        {
            issub1 = false;
            cnt++;
        }
        prefix[i] = prefix[i - 1] + a[i];
    }

    if (issub1)
    {
        subtask1();
        return;
    }
    if (k == 1)
    {
        subtask3();
        return;
    }
    if (cnt <= 1)
    {
        subtask2();
        return;
    }
    subtask456();
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen((name + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen((name + ".out").c_str(), "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