| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 418646 | JediMaster11 | Meetings (IOI18_meetings) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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>
ll maxx[100000][10000]; // 750000
ll recur2(int l, int r, vint h)
{
if (r - l == 1)
{
return h[l];
}
ll numOnes = 0;
ll maxOnes = -1;
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] != 0)
{
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);
// }
int maxx = 0;
fo(i, 0, h.size())
{
maxx = max(maxx, h[i]);
}
if (maxx == 2)
{
fo(i, 0, (int)numMeetings)
{
minCosts.push_back(recur2(l[i], r[i] + 1, h));
}
}
else
{
fo(i, 0, (int)numMeetings)
{
minCosts.push_back(recur(l[i], r[i] + 1, h));
}
}
return minCosts;
}