oj.uz

Submission #418572

# Submission time Handle Problem Language Result Execution time Memory
418572 2021-06-05T14:31:27 Z JediMaster11 Meetings (IOI18_meetings) C++17
19 / 100
 5500 ms 507328 KB 
#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[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];
    }

    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]);
//     }
// }

Compilation message

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++)
......
   65 |     fo(i, 0, aves.size())
      |        ~~~~~~~~~~~~~~~~~               
meetings.cpp:65:5: note: in expansion of macro 'fo'
   65 |     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++)
......
   90 |     fo(i, 0, h.size())
      |        ~~~~~~~~~~~~~~                  
meetings.cpp:90:5: note: in expansion of macro 'fo'
   90 |     fo(i, 0, h.size())
      |     ^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 42 ms 73428 KB Output is correct
3 Correct 42 ms 73372 KB Output is correct
4 Correct 44 ms 73632 KB Output is correct
5 Correct 42 ms 73336 KB Output is correct
6 Correct 41 ms 73156 KB Output is correct
7 Correct 40 ms 73136 KB Output is correct
8 Correct 39 ms 73136 KB Output is correct
9 Correct 39 ms 73132 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 42 ms 73428 KB Output is correct
3 Correct 42 ms 73372 KB Output is correct
4 Correct 44 ms 73632 KB Output is correct
5 Correct 42 ms 73336 KB Output is correct
6 Correct 41 ms 73156 KB Output is correct
7 Correct 40 ms 73136 KB Output is correct
8 Correct 39 ms 73136 KB Output is correct
9 Correct 39 ms 73132 KB Output is correct
10 Correct 257 ms 199092 KB Output is correct
11 Correct 223 ms 199268 KB Output is correct
12 Correct 223 ms 199036 KB Output is correct
13 Correct 268 ms 199100 KB Output is correct
14 Correct 3835 ms 198836 KB Output is correct
15 Correct 234 ms 198952 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Execution timed out 5612 ms 507328 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Execution timed out 5612 ms 507328 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 42 ms 73428 KB Output is correct
3 Correct 42 ms 73372 KB Output is correct
4 Correct 44 ms 73632 KB Output is correct
5 Correct 42 ms 73336 KB Output is correct
6 Correct 41 ms 73156 KB Output is correct
7 Correct 40 ms 73136 KB Output is correct
8 Correct 39 ms 73136 KB Output is correct
9 Correct 39 ms 73132 KB Output is correct
10 Correct 257 ms 199092 KB Output is correct
11 Correct 223 ms 199268 KB Output is correct
12 Correct 223 ms 199036 KB Output is correct
13 Correct 268 ms 199100 KB Output is correct
14 Correct 3835 ms 198836 KB Output is correct
15 Correct 234 ms 198952 KB Output is correct
16 Correct 2 ms 2636 KB Output is correct
17 Execution timed out 5612 ms 507328 KB Time limit exceeded
18 Halted 0 ms 0 KB -