Submission #1290653

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290653		thuy_k31	Feast (NOI19_feast)	C++20	100 / 100	109 ms	5152 KiB

feast

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) v.begin(), v.end()
const int N = 1e6 + 9;
const int MOD = 1e9 + 7;
const long long INF = 1e18;

int n, k;
int a[N];
long long pref[N];
pair <long long, long long> dp[2];
pair <long long, long long> cal (long long val)
{
    dp[1] = {0, 0};
    dp[0] = {-INF, -INF};

    for (int i = 1; i <= n; ++i) {
        dp[0] = max(dp[0], {dp[1].first - pref[i - 1] - val, dp[1].second});

        dp[1] = max(dp[1], {dp[0].first + pref[i], dp[0].second - 1});

    }
    return dp[1];
}
signed main()
{
    #define task "task"
    if (fopen(task".inp","r"))
    {
        freopen (task".inp","r",stdin);
        freopen (task".out","w",stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        pref[i] = pref[i - 1] + a[i];
    }
    long long lo = 0, hi = 1e18;
    long long ans = -INF;
    long long pos = 0;
    while (lo <= hi) {
        long long mid = (lo + hi) >> 1;
        pair <long long, long long> cur = cal(mid);
        if (-cur.second >= k) {
            lo = mid + 1;
            pos = mid;
        }
        else hi = mid - 1;;
    }
    cout << cal(pos).first + k * pos;
}
/**

**/

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:33:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen (task".inp","r",stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
feast.cpp:34:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         freopen (task".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: 29 / 29