제출 #1269252

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269252		onim	Feast (NOI19_feast)	C++17	12 / 100	71 ms	7396 KiB

feast

//         author : MOHAMMED OMAR FAIAZ ONIM
//         gmail : [e-mail]
//         戦え

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
const long long INF = 1e18;
#define ll long long

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int testcases = 1;
    // cin>>testcases;

    while (testcases--)
    {
        ll n, k;
        cin >> n >> k;

        vector<ll> v(n);
        vector<ll> comp;
        for (ll i = 0; i < n; i++)
        {
            cin >> v[i];
        }
        ll sum = 0, l = 0, ok = 1;

        vector<ll> neg;
        vector<ll> poscomp;
        ll sz = 0;
        while (l < n)
        {
            if (ok)
            {
                while (ok && l < n && v[l] >= 0)
                {
                    sz++;
                    sum += v[l];
                    l++;
                }
                comp.push_back(sum);
                poscomp.push_back(sum);
            }
            else
            {
                while (!ok && l < n && v[l] < 0)
                {
                    neg.push_back(v[l]);
                    sum += v[l];
                    l++;
                }
                comp.push_back(sum);
            }
            sum = 0;
            ok ^= 1;
        }

        if (k >= poscomp.size())
        {
            ll ans = accumulate(poscomp.begin(), poscomp.end(), 0ll);
            ll rem = max(k - sz, 0ll);
            sort(neg.begin(), neg.end());

            while (rem--)
            {
                ans += neg.back();
                neg.pop_back();
            }
            cout << ans << "\n";
            return 0;
        }

        // sz = poscomp.size();

        // cout<<sz<<endl;

        ll y = 50;

        while (y--)
        {

            for (ll i = 0; i < comp.size(); i++)
            {
                if (comp[i] < 0 && i - 1 >= 0 && i + 1 < comp.size() && (comp[i - 1] + comp[i + 1] + comp[i]) > max(comp[i - 1], comp[i+1]))
                {
                    // cout<<comp[i-1]<<" "<<comp[i]<<" "<<comp[i+1]<<" "<<endl;
                    comp[i + 1] = comp[i - 1] + comp[i + 1] + comp[i];
                    comp[i - 1] = 0;
                    comp[i] = 0;
                    // cout<<"ok"<<endl;
                }
            }

            // for (auto &to : comp)
            //     cout << to << " ";
            // cout << endl;

            vector<ll> v;

            for (auto &i : comp)
            {
                if (i != 0)
                    v.push_back(i);
            }

            comp = v;

            for (ll i = comp.size() - 1; i >= 0; i--)
            {
                if (comp[i] < 0 && i - 1 >= 0 && i + 1 < comp.size() && (comp[i - 1] + comp[i + 1] + comp[i]) > max(comp[i - 1], comp[i+1]))
                {
                    comp[i + 1] = 0;
                    comp[i] = 0;
                    comp[i - 1] = comp[i - 1] + comp[i + 1] + comp[i];
                }
            }

            v.clear();

            for (auto &i : comp)
            {
                if (i != 0)
                    v.push_back(i);
            }
            comp = v;
        }

        sort(comp.begin(), comp.end());

        ll ans = 0;
        while (k--)
        {
            ans += comp.back();
            comp.pop_back();
        }
        cout << ans << endl;
    }
}

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