Submission #1226719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226719		andrei_iorgulescu	Candies (JOI18_candies)	C++20	0 / 100	0 ms	576 KiB

candies

#include <bits/stdc++.h>

using namespace std;

#define int long long

int inf = 1e18;

int bln = 100;

vector<pair<int, int>> var_mij = {{0, 0}, {0, 1}, {1, 0}};

struct mydp
{
    vector<int> dp[2][2];///dp[x1][x2][i] = daca iau / nu primul / ultimul, si in total iau i, ce profit maxim fac?
};

int n, a[200005];

mydp solve(int l, int r)
{
    int bnd = (r - l + 1) / 2 + (r - l + 1) % 2;
    mydp aux;
    for (int x1 = 0; x1 < 2; x1++)
        for (int x2 = 0; x2 < 2; x2++)
            aux.dp[x1][x2].resize(bnd + 1);
    for (int x1 = 0; x1 < 2; x1++)
        for (int x2 = 0; x2 < 2; x2++)
            for (int i = 0; i <= bnd; i++)
                aux.dp[x1][x2][i] = -inf;
    if (l == r)
    {
        aux.dp[0][0][0] = 0;
        aux.dp[1][1][1] = a[l];
    }
    else
    {
        int mij = (l + r) / 2;
        mydp L = solve(l, mij);
        mydp R = solve(mij + 1, r);
        for (int x1 = 0; x1 < 2; x1++)
        {
            for (int x2 = 0; x2 < 2; x2++)
            {
                int xant = 0, yant = 0;
                if (x1 + x2 == 0)
                    aux.dp[x1][x2][0] = 0;
                for (int i = 1; i <= bnd; i++)
                {
                    for (int xcr = xant - bln; xcr <= xant + bln; xcr++)
                    {
                        int ycr = i - xcr;
                        if (xcr >= 0 and ycr >= 0 and xcr < L.dp[0][0].size() and ycr < R.dp[0][0].size())
                        {
                            for (auto it : var_mij)
                            {
                                aux.dp[x1][x2][i] = max(aux.dp[x1][x2][i], L.dp[x1][it.first][xcr] + R.dp[it.second][x2][ycr]);
                                //cout << x1 << ' ' << x2 << ' ' << i << ' ' << aux.dp[x1][x2][i] << endl;
                            }
                        }
                    }
                }
            }
        }
        return aux;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    mydp ans = solve(1, n);
    for (int i = 1; i <= n / 2 + n % 2; i++)
    {
        int ct = 0;
        for (int x1 = 0; x1 < 2; x1++)
            for (int x2 = 0; x2 < 2; x2++)
                ct = max(ct, ans.dp[x1][x2][i]);
        cout << ct << '\n';
    }
    return 0;
}

Compilation message (stderr)

candies.cpp: In function 'mydp solve(long long int, long long int)':
candies.cpp:34:25: warning: control reaches end of non-void function [-Wreturn-type]
   34 |         aux.dp[1][1][1] = a[l];

• Subtask 1: 0 / 8
• Subtask 2: 0 / 92