Submission #418638

#	Time	Username	Problem	Language	Result	Execution time	Memory
418638		JediMaster11	Meetings (IOI18_meetings)	C++17	0 / 100	110 ms	3840 KiB

meetings

#include <bits/stdc++.h>
// #include "meetings.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>

ll maxx[10000][10000]; // 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];
    }

    ll maxH = -1;

    fo(i, l, r)
    {

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

    vector<pair<pair<int, int>, ll>> aves;
    // stores the left and right, and then the sum of the middle

    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 = 0ll + maxH * (r - l) + 1;

    fo(i, 0, aves.size())
    {
        ll maxtmp = 0ll + 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();

    minCosts.reserve(numMeetings);

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

    fo(i, 0, (int)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};

//     int n, q;

//     cin >> n >> q;

//     vint h;

//     int tmpa;
//     fo(i, 0, n)
//     {
//         cin >> tmpa;
//         h.push_back(tmpa);
//     }

//     vint l, r;
//     int lH, rH;
//     fo(i, 0, q)
//     {
//         cin >> lH >> rH;
//         l.push_back(lH);
//         r.push_back(rH);
//     }

//     // vint h = {877914575};
//     // vint l = {0};
//     // vint r = {(int)h.size() - 1};

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

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

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