Submission #418405

#	Time	Username	Problem	Language	Result	Execution time	Memory
418405		JediMaster11	Meetings (IOI18_meetings)	C++17	0 / 100	5520 ms	255600 KiB

meetings

#include <bits/stdc++.h>

using namespace std;
#define fo(a, b, c) for (int a = b; a < (int)c; a++)
#define ll long long
#define print(x) cout << x << "\n";
#define vint vector<int>
#define vll vector<long long>




vint maxx[100000]; // 750000

ll recur(int l, int r, vint h)
{ // r is non-inclsuive

    if (r - l == 1)
    {
        return h[l];
    }
    else if (r == l)
    {
        return 0;
    }

    if (maxx[l][r-1] != -1)
    {

        return maxx[l][r-1];
    }

    int maxH = -1;

    fo(i, l, r)
    {

        maxH = max(maxH, h[i]);
    }

    vector<pair<pair<int, int>, ll>> aves;

    int leftH = l;
    fo(i, l, r)
    {
        if (h[i] == maxH)
        {
            if (i == l || h[i] != h[i - 1])
            {

                ll tmp = recur(leftH, i, h);
                aves.push_back({{leftH, i}, tmp});
            }
            leftH = i + 1;
        }
    }

    if (leftH != r)
    {
        ll tmp = recur(leftH, r, h);
        aves.push_back({{leftH, r}, tmp});
    }

    // int index=-1;
    ll smallest = maxH * (r - l) + 1;

    fo(i, 0, aves.size())
    {
        ll maxtmp = (ll) + aves[i].second + maxH * ((r - aves[i].first.second) + (aves[i].first.first - l));

        if (maxtmp < smallest)
        {
            smallest = maxtmp;
        }
    }

    maxx[l][r-1] = smallest;
    return smallest;
}

// h - heights
// l, r - left and right bounds of each meeting

vll minCosts;
vll minimum_costs(vint h, vint l, vint r)
{

    int numMeetings = l.size();

    // compute(h);

    fo(i, 0, h.size())
    {
        maxx[i].assign(h.size(), -1);
    }

    minCosts.reserve(numMeetings);

    fo(i, 0, numMeetings)
    {

        minCosts.push_back(recur(l[i], r[i] + 1, h));
    }

    return minCosts;
}

// int main()
// {

//     ios::sync_with_stdio(0);
//     cin.tie(0);

//     // vint h = {2, 5, 1, 6, 8, 1, 4};
//     // vint l = {0};
//     // vint r = {6};

//     vint h = {50, 10, 50, 30, 50, 10, 50};
//     vint l = {0};
//     vint r = {(int) h.size()-1};

//     vll tmp = minimum_costs(h, l, r);

    

//     fo(i, 0, l.size())
//     {
//         print(tmp[i]);
//     }
// }

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40