제출 #1133595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133595		minhcool	Feast (NOI19_feast)	C++20	100 / 100	376 ms	29976 KiB

feast

#define local
#ifndef local
#include ""
#endif
#include <bits/stdc++.h>
// using namespace __gnu_pbds;
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int rnd(int l, int r)
{
    int temp = rng() % (r - l + 1);
    return abs(temp) + l;
}

int n, k, a[N];

vector<vector<int>> cal(int l, int r)
{ // from left to right: (0,0), (0,1), (1,0), (1,1)
    if (l == r)
    {
        vector<vector<int>> v;
        v.pb({0, -oo});
        v.pb({-oo, -oo});
        v.pb({-oo, -oo});
        v.pb({-oo, a[l]});
        return v;
    }
    int mid = (l + r) >> 1;
    vector<vector<int>> cal1 = cal(l, mid), cal2 = cal(mid + 1, r);
    vector<vector<int>> ans;
    for (int i = 0; i <= 3; i++)
    {
        vector<int> temp;
        temp.resize(r - l + 2);
        for (int j = 0; j < temp.size(); j++)
            temp[j] = -oo;
        ans.pb(temp);
    }
    int left_len = (mid - l + 1), right_len = (r - mid);
    // cout << "START " << l << " " << r << "\n";
    //  int want = (l + r + 1) >> 1;
    for (int le = 0; le < 2; le++)
    {
        for (int ri = 0; ri < 2; ri++)
        {
            for (int mile = 0; mile < 2; mile++)
            {
                for (int miri = 0; miri < 2; miri++)
                {
                    int er = mile & miri;
                    int cur_opt = 0;
                    int temp1 = ((left_len + 1 - !(le & mile)) / 2), temp2 = (right_len + 1 - !(ri & miri)) / 2;
                    //  cout << le << " " << ri << " " << mile << " " << miri << " " << temp1 << " " << temp2 << "\n";
                    for (int tol = 0; tol <= temp1 + temp2 - er; tol++)
                    {
                        while (tol - cur_opt + er > temp2)
                            cur_opt++;
                        while (cur_opt < min(temp1, tol + er))
                        {
                            //			cout << cur_opt << "\n";
                            int val1 = cal1[(le << 1) | mile][cur_opt] + cal2[(miri << 1) | ri][tol - cur_opt + er];
                            int val2 = cal1[(le << 1) | mile][cur_opt + 1] + cal2[(miri << 1) | ri][tol - cur_opt - 1 + er];
                            //	cout << val1 << " " << val2 << "\n";
                            if (val1 < val2)
                                cur_opt++;
                            else
                                break;
                        }
                        //  cout << le << " " << ri << " " << mile << " " << miri << " " << tol << " " << cur_opt << " " << tol - cur_opt + er << " " << cal1[(le << 1) | mile][cur_opt] + cal2[(miri << 1) | ri][tol - cur_opt + er] << "\n";
                        ans[(le << 1) | ri][tol] = max(ans[(le << 1) | ri][tol], cal1[(le << 1) | mile][cur_opt] + cal2[(miri << 1) | ri][tol - cur_opt + er]);
                    }
                }
            }
        }
    }
    // cout << l << " " << r << "\n";
    for (int i = 0; i < 4; i++)
    {
        //  cout << "OK ";
        // for (int j = 0; j < ans[i].size(); j++)
        //    cout << ans[i][j] << " ";

        // cout << "\n";
    }
    return ans;
}

#ifdef local
void process()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    vector<vector<int>> v = cal(1, n);
    int answer = -oo;
    for (int i = 0; i <= k; i++)
        answer = max(answer, max({v[0][i], v[1][i], v[2][i], v[3][i]}));
    cout << answer << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
   // freopen("temp.inp", "r", stdin);
  //  freopen("temp.out", "w", stdout);
    process();
}
#endif

• 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