oj.uz

답안 #418713

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
418713 2021-06-05T18:58:19 Z JediMaster11 모임들 (IOI18_meetings) C++17
19 / 100
 3825 ms 786436 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[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);

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

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

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 40 ms 71276 KB Output is correct
3 Correct 38 ms 71244 KB Output is correct
4 Correct 37 ms 71304 KB Output is correct
5 Correct 38 ms 71292 KB Output is correct
6 Correct 38 ms 71068 KB Output is correct
7 Correct 36 ms 70980 KB Output is correct
8 Correct 35 ms 71108 KB Output is correct
9 Correct 34 ms 71056 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 40 ms 71276 KB Output is correct
3 Correct 38 ms 71244 KB Output is correct
4 Correct 37 ms 71304 KB Output is correct
5 Correct 38 ms 71292 KB Output is correct
6 Correct 38 ms 71068 KB Output is correct
7 Correct 36 ms 70980 KB Output is correct
8 Correct 35 ms 71108 KB Output is correct
9 Correct 34 ms 71056 KB Output is correct
10 Correct 259 ms 196996 KB Output is correct
11 Correct 228 ms 197176 KB Output is correct
12 Correct 225 ms 196952 KB Output is correct
13 Correct 277 ms 196932 KB Output is correct
14 Correct 3825 ms 196912 KB Output is correct
15 Correct 229 ms 196860 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 802 ms 505140 KB Output is correct
3 Runtime error 410 ms 786436 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 802 ms 505140 KB Output is correct
3 Runtime error 410 ms 786436 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 40 ms 71276 KB Output is correct
3 Correct 38 ms 71244 KB Output is correct
4 Correct 37 ms 71304 KB Output is correct
5 Correct 38 ms 71292 KB Output is correct
6 Correct 38 ms 71068 KB Output is correct
7 Correct 36 ms 70980 KB Output is correct
8 Correct 35 ms 71108 KB Output is correct
9 Correct 34 ms 71056 KB Output is correct
10 Correct 259 ms 196996 KB Output is correct
11 Correct 228 ms 197176 KB Output is correct
12 Correct 225 ms 196952 KB Output is correct
13 Correct 277 ms 196932 KB Output is correct
14 Correct 3825 ms 196912 KB Output is correct
15 Correct 229 ms 196860 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 802 ms 505140 KB Output is correct
18 Runtime error 410 ms 786436 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -