Submission #418718

#	Time	Username	Problem	Language	Result	Execution time	Memory
418718		JediMaster11	Meetings (IOI18_meetings)	C++17	19 / 100	5582 ms	504520 KiB

meetings

#include <bits/stdc++.h>
// #include "meetings.h"

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

vll maxx[10000]; // 750000

ll recur2(int l, int r, vint h)
{

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

    ll numOnes = 0;
    ll maxOnes = 0;
    bool onOne = false;

    fo(i, l, r)
    {

        if (h[i] == 1)
        {

            if (onOne)
            {
                numOnes++;
            }
            else
            {
                numOnes = 1;
                onOne = true;
            }
        }
        else if (onOne)
        {
            onOne = false;
            maxOnes = max(maxOnes, numOnes);
            numOnes = 0;
        }
    }
    if (onOne)
    {
        onOne = false;
        maxOnes = max(maxOnes, numOnes);
        numOnes = 0;
    }

    return maxOnes + 2 * (r - l - maxOnes);
}

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);

    int maxH = 0;

    fo(i, 0, h.size())
    {
        maxH = max(maxH, h[i]);
    }

    if (maxH <= -1)
    {
        fo(i, 0, (int)numMeetings)
        {

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

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

        fo(i, 0, (int)numMeetings)
        {

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

    return minCosts;
}

Compilation message (stderr)

meetings.cpp: In function 'long long int recur(int, int, std::vector<int>)':
meetings.cpp:5:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define fo(a, b, c) for (int a = b; a < c; a++)
......
  111 |     fo(i, 0, aves.size())
      |        ~~~~~~~~~~~~~~~~~               
meetings.cpp:111:5: note: in expansion of macro 'fo'
  111 |     fo(i, 0, aves.size())
      |     ^~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:5:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define fo(a, b, c) for (int a = b; a < c; a++)
......
  138 |     fo(i, 0, h.size())
      |        ~~~~~~~~~~~~~~                  
meetings.cpp:138:5: note: in expansion of macro 'fo'
  138 |     fo(i, 0, h.size())
      |     ^~
meetings.cpp:5:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define fo(a, b, c) for (int a = b; a < c; a++)
......
  154 |         fo(j, 0, h.size())
      |            ~~~~~~~~~~~~~~              
meetings.cpp:154:9: note: in expansion of macro 'fo'
  154 |         fo(j, 0, h.size())
      |         ^~

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