제출 #573594

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
573594		danikoynov	Feast (NOI19_feast)	C++14	63 / 100	250 ms	14348 KiB

feast

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 3e5 + 10;

int n;
ll k, a[maxn], dp[maxn][2], cnt[maxn][2], par[maxn];

pair < ll, int > calc(ll cost)
{
    dp[0][1] = -1e18;
    for (int i = 1; i <= n; i ++)
    {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
        dp[i][1] = max(dp[i - 1][0] - cost, dp[i - 1][1]) + a[i];
        cnt[i][1] = cnt[i][0] = 0;
        if (dp[i - 1][0] == dp[i][0])
            cnt[i][0] = max(cnt[i][0], cnt[i - 1][0]);
        if (dp[i - 1][1] == dp[i][0])
            cnt[i][0] = max(cnt[i][0], cnt[i - 1][1]);
        if (dp[i - 1][0] - cost + a[i] == dp[i][1])
            cnt[i][1] = max(cnt[i][1], cnt[i - 1][0] + 1);
        if (dp[i - 1][1] + a[i] == dp[i][1])
            cnt[i][1] = max(cnt[i][1], cnt[i - 1][1]);
    }

    //for (int i = 1; i <= n; i ++)
       // cout << dp[i][0] << " - " << dp[i][1] << endl;
        pair < ll, int > ans = {dp[1][0], cnt[1][0]};
    for (int i = 1; i <= n; i ++)
        for (int j = 0; j < 2; j ++)
        if (make_pair((ll)dp[i][j], (int)cnt[i][j]) > ans)
            ans = {dp[i][j], cnt[i][j]};
    return ans;
    /**for (int i = 1; i <= n; i ++)
    {
        dp[i] = dp[i - 1];
        cnt[i] = cnt[i - 1];
        for (int j = 1; j <= i; j ++)
        {
            ll sum = dp[j - 1] - cost + par[i] - par[j - 1];
            if (sum > dp[i])
                dp[i] = sum;
            if (sum == dp[i])
                cnt[i] = max(cnt[i], cnt[j - 1] + 1);
        }
    }
    pair < ll, int > ans = {dp[1], cnt[1]};
    for (int i = 2; i <= n; i ++)
        if (make_pair((ll)dp[i], (int)cnt[i]) > ans)
            ans = {dp[i], cnt[i]};
    return ans;*/
}
void solve()
{
    cin >> n >> k;

    ll cnt = 0, neg = 0;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        if (a[i] >= 0)
            cnt ++;
        else
            neg ++;
        par[i] = par[i - 1] + a[i];
    }
    k = min(cnt, k);

    if (neg == 1)
    {
        ll f1 = 0, f2 = 0, pos = -1;
        for (int i = 1; i <= n; i ++)
        {
            if (a[i] < 0)
            {
                pos = i;
                break;
            }
            f1 += a[i];
        }

        for (int i = n; i > 0; i --)
        {
            if (a[i] < 0)
            {
                pos = i;
                break;
            }
            f2 += a[i];
        }

        if (pos == -1)
        {
            cout << f1 << endl;
        }
        else
        {
            if (k == 2)
            cout << f1 + f2 << endl;
            else
                cout << max(f1, max(f2, f1 + f2 + a[pos]));
        }
        return;
    }

    ll lf = 0, rf = 1e12;
    while(lf <= rf)
    {
        ll mf = (lf + rf) / 2;
        pair < double, int > cur = calc(mf);
        if (cur.second >= k)
            lf = mf + 1;
        else
            rf = mf - 1;
    }

    double p1 = lf - 1, p2 = lf;
    pair < ll, int > cur1 = calc(p1), cur2 = calc(p2);
    cur1.first = cur1.first + cur1.second * p1;
    cur2.first = cur2.first + cur2.second * p2;
    double part = 1.0 - (double)(cur1.second - k) / (double)(cur1.second - cur2.second);
    double slope = (cur1.first - cur2.first);
    double ans = cur2.first + slope * part;
    ///cout << cur1.second << " " << cur2.second << " " << part << " " << cur1.second - k << " " << k << endl;
    if (cur1.second == cur2.second)
    {
        cout << cur1.first << endl;
        return;
    }
    cout << (ll)round(ans) << endl;
}

int main()
{
    solve();
    return 0;
}
/**
7 1
3 4 -1 2 3 -5 1
*/

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