Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.67/15: Рейтинг темы: голосов - 15, средняя оценка - 4.67
0 / 0 / 0
Регистрация: 05.09.2024
Сообщений: 16

Ошибка выполнения

05.09.2024, 19:40. Показов 4338. Ответов 38

Студворк — интернет-сервис помощи студентам
Здравствуйте. Тестирующая система выдает вердикт "ошибка выполнения". Я никак не понимаю, почему это может происходить. Ошибок при работе с памятью не нашел, переполнений переменных не должно быть (1 <= w,h <= 109, 0 <= n,m <= 105, 1 <= k <= n*m)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream> 
#include <algorithm> 
#include <vector> 
#define ll long long 
using namespace std;
int main() { 
    ll w, h; int n, m; ll k; 
    cin >> w >> h >> n >> m >> k;
    vector<ll> len; vector<ll> arr;
    ll last = 0; ll line;
    for (int i = 0; i < n; i++) {
        cin >> line;
        len.push_back(line - last); 
        last = line;
    }
    len.push_back(w - last);
    last = 0; 
    for (int i = 0; i <= m; i++) {
        if (i < m) cin >> line;
        else line = h;
        ll curl = line - last; 
        for (ll j : len) {
            arr.push_back(curl * j);
        }
        last = line;
    }
    sort(arr.rbegin(), arr.rend()); 
    cout << arr[k - 1] << " " << arr[0] << endl;
}
0
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
05.09.2024, 19:40
Ответы с готовыми решениями:

Укажите где ошибка (ошибка во время выполнения программы)
Здравствуйте, помогите пожалуйста найти ошибки в коде которые возникаю при выполнении программы Картинка с ошибкой внизу поста. Код: ...

Ошибка выполнения
#include &lt;iostream&gt; #include &lt;vector&gt; int main() { int n, k; std::cin &gt;&gt; n &gt;&gt; k; std::string uniforms; ...

Ошибка во время выполнения
есть такой вот кусочек кода, компилириуются без ошибок, а в процессе выполнения ругает int t = 0; ifstream fin; fin.open...

38
0 / 0 / 0
Регистрация: 05.09.2024
Сообщений: 16
06.09.2024, 19:19  [ТС]
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от SmallEvil Посмотреть сообщение
Наша матрица (воображаемая) :
Все равно не понял Ваше решение. Откуда взялась эта матрица? Я так понимаю, это результаты умножения длин графств на высоты?
0
 Аватар для Storm Screamer
5841 / 1599 / 127
Регистрация: 21.04.2013
Сообщений: 9,263
06.09.2024, 19:19
Цитата Сообщение от SmallEvil Посмотреть сообщение
Уже ж писали, что упрешься в память.
Другой вариант:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
int main() {
    // Чтение входных данных
    int w, h;
    cin >> w >> h;
    
    int n, m;
    cin >> n >> m;
    
    int k;
    cin >> k;
    
    vector<int> x(n), y(m);
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> y[i];
    }
    
    // Добавление границ королевства
    x.push_back(w);
    y.push_back(h);
    
    // Вычисление размеров графств
    vector<long long> widths(n + 1), heights(m + 1);
    for (int i = 0; i <= n; ++i) {
        if (i == 0) {
            widths[i] = x[i];
        } else {
            widths[i] = x[i] - x[i - 1];
        }
    }
    
    for (int i = 0; i <= m; ++i) {
        if (i == 0) {
            heights[i] = y[i];
        } else {
            heights[i] = y[i] - y[i - 1];
        }
    }
    
    // Использование priority queue для хранения k самых больших площадей
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            long long area = widths[i] * heights[j];
            if (pq.size() < k) {
                pq.push(area);
            } else if (area > pq.top()) {
                pq.pop();
                pq.push(area);
            }
        }
    }
    
    // Получение k самых больших площадей
    vector<long long> largest_areas;
    while (!pq.empty()) {
        largest_areas.push_back(pq.top());
        pq.pop();
    }
    
    // Сортировка вектор largest_areas по возрастанию
    sort(largest_areas.begin(), largest_areas.end());
    
    // Вывод площадей графств для младшего и старшего сыновей
    cout << largest_areas[0] << " " << largest_areas[k - 1] << endl;
    
    return 0;
}
0
0 / 0 / 0
Регистрация: 05.09.2024
Сообщений: 16
06.09.2024, 19:33  [ТС]
Цитата Сообщение от Storm Screamer Посмотреть сообщение
Другой вариант:
Я подозреваю, что это опять-таки не будет работать из-за создания вектора largest_areas, размер которого может быть очень большим.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13236 / 6868 / 1827
Регистрация: 18.10.2014
Сообщений: 17,413
06.09.2024, 20:47
Цитата Сообщение от Storm Screamer Посмотреть сообщение
Другой вариант:
Если бы задачу можно было решать через O(k) памяти, то

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <vector>
#include <set>
#include <numeric>
#include <algorithm>
#include <iostream>
 
int main()
{
  unsigned w, h, n, m; 
  unsigned long long k;
  std::cin >> w >> h >> n >> m >> k;
  
  std::vector<unsigned> ws(n + 2);
  for (unsigned i = 1; i <= n; ++i)
    std::cin >> ws[i];
    
  ws.front() = 0;
  ws.back() = w;
  std::sort(ws.begin() + 1, ws.end() - 1);
  std::adjacent_difference(ws.begin(), ws.end(), ws.begin());
 
  std::vector<unsigned> hs(m + 2);
  for (unsigned j = 1; j <= m; ++j)
    std::cin >> hs[j];
    
  hs.front() = 0;
  hs.back() = h;
  std::sort(hs.begin() + 1, hs.end() - 1);
  std::adjacent_difference(hs.begin(), hs.end(), hs.begin());
  
  std::multiset<unsigned long long> as;
  
  for (unsigned i = 1; i <= n + 1; ++i)
    for (unsigned j = 1; j <= m + 1; ++j)
    {
      as.insert((unsigned long long) ws[i] * hs[j]);
      if (as.size() > k)
        as.erase(as.begin());
    }
  
  std::cout << *as.begin() << " " << *std::prev(as.end()) << std::endl;
}
Но это нежизнеспособно из-за больших пределов на k.
0
 Аватар для SmallEvil
4086 / 2975 / 813
Регистрация: 29.06.2020
Сообщений: 11,000
06.09.2024, 20:58
Цитата Сообщение от scufford Посмотреть сообщение
Все равно не понял Ваше решение. Откуда взялась эта матрица?
Матрица воображаемая. Но мой подход, явно ошибочный.
Немного поразмыслив, не так то просто создать большое количество прямоугольников разной площади.
Думаю можно попробовать закинуть их (площади) в std::map;
Хотя решение всё равно тяжеловесное, но может пройти, из за соображения выше (что невозможно создать множество различных по площади прямоугольников).
Плюс ещё вопрос, границы воображаемые или занимают точку (единицу измерения) ?
0
 Аватар для SmallEvil
4086 / 2975 / 813
Регистрация: 29.06.2020
Сообщений: 11,000
06.09.2024, 21:01
Цитата Сообщение от scufford Посмотреть сообщение
Я так понимаю, это результаты умножения длин графств на высоты?
Да.
Вот например наше королевство и его дележ, уже отсортированных высот и ширин.
Миниатюры
Ошибка выполнения  
0
 Аватар для SmallEvil
4086 / 2975 / 813
Регистрация: 29.06.2020
Сообщений: 11,000
06.09.2024, 21:12
p.s. задачка то с подвохом
Но в лоб всё равно не стоило решать. Нужно в полулоб

Добавлено через 9 минут
Чисто ради прикола
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <cstdint>
#include <map>
#include <vector>
#include <functional>
 
int main() {
    using ull_t = std::uint64_t;
    ull_t w, h, n, m, k;
    std::cin >> w >> h >> n >> m >> k;
    std::map<ull_t, unsigned, std::greater<ull_t>> areas;
    // input grid section
 
    {
        std::vector<ull_t> widths(n+1);
        ull_t m_prev = 0, n_prev = 0;
        for(ull_t i = 0, xn; i != n; ++i){
            std::cin >> xn;
            widths[i] = xn - n_prev;
            n_prev = xn;
        }
        widths[n] = w - n_prev;
 
        for(ull_t j = 0, xm; j != m; ++j){
            std::cin >> xm;
            for(ull_t i = 0; i <= n; ++i){
               ull_t height = xm - m_prev; 
               ++areas[height * widths[i]];
            }
            m_prev = xm;
        }
        for(ull_t i = 0, height = h - m_prev; i <= n; ++i)
           ++areas[height * widths[i]];     
    }
    // end input dection
    
    ull_t max{areas.begin()->first}, min{max};
 
    for(const auto &data : areas) {
        if (k <= data.second){
         min = data.first;
         break;
        }
      k -= data.second;
    }
    std::cout << min << ' ' << max << std::endl;
}
0
0 / 0 / 0
Регистрация: 05.09.2024
Сообщений: 16
06.09.2024, 21:21  [ТС]
Цитата Сообщение от SmallEvil Посмотреть сообщение
Думаю можно попробовать закинуть их (площади) в std::map;
Уже пробовал, просто с map не проходит по времени, если же использовать unordered_map, то нужно еще создавать вектор пар, который потом надо сортировать, короче, тоже не проходит по времени, но уже на более позднем тесте.

Цитата Сообщение от SmallEvil Посмотреть сообщение
Плюс ещё вопрос, границы воображаемые или занимают точку (единицу измерения) ?
Если рассматривать клеточное поле, то они проходят между клетками
0
 Аватар для SmallEvil
4086 / 2975 / 813
Регистрация: 29.06.2020
Сообщений: 11,000
06.09.2024, 21:32
Цитата Сообщение от scufford Посмотреть сообщение
Уже пробовал, просто с map не проходит по времени,
И мой код пробовали ?
Он немного оптимизирован.
0
0 / 0 / 0
Регистрация: 05.09.2024
Сообщений: 16
06.09.2024, 21:46  [ТС]
Цитата Сообщение от SmallEvil Посмотреть сообщение
И мой код пробовали ?
Нет, еще не пробовал.

А решение с map я реализовал криво, сейчас оптимизирую.

Добавлено через 8 минут
Цитата Сообщение от SmallEvil Посмотреть сообщение
И мой код пробовали ?
Теперь попробовал. И он, и решение с map не проходит по времени.

Если что, вот мое решение с map. Вроде все нормально написано, но не проходит

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <map>
#define ll long long
#define quan second
#define val first
using namespace std;
struct Compare {
    bool operator()(const ll& a, const ll& b) const {
        return a > b; 
    }
};
int main() { 
    int w, h, n, m, k; 
    cin >> w >> h >> n >> m >> k;
    map<ll, ll, Compare> sq; 
    int len[n+1];
    int last, line, ind = 0;
    for (int i = 0; i < n; i++) {
        cin >> line;
        len[ind++] = line - last; 
        last = line;
    }
    len[n] = w - last;
    last = 0;
    ll curl;
    for (int i = 0; i <= m; i++) {
        if (i < m) cin >> line;
        else line = h;
        curl = line - last; 
        for (ll j : len) {
            sq[curl * j]++;
        }
        last = line;
    }
    ll cnt = 0, older = -1, junior = -1;
    for (auto i: sq) {
        if (older == -1) {
            older = i.val;
        }
        if (cnt < k && k <= cnt + i.quan) {
            junior = i.val; 
            break;
        }
        cnt += i.quan; 
    }
    cout << junior << " " << older << endl;
}
0
 Аватар для SmallEvil
4086 / 2975 / 813
Регистрация: 29.06.2020
Сообщений: 11,000
06.09.2024, 22:06
Значит нужно искать лазейку. Но уже не сегодня.

Добавлено через 5 минут
Цитата Сообщение от scufford Посмотреть сообщение
#define ll long long
Знаковый тип отпадает сразу.
Потому что можно w и h получить 109 и поделить на 4 части, и получить один квадрат со сторонами (109 - 1) Х (109 - 1.
И угадай что будет.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13236 / 6868 / 1827
Регистрация: 18.10.2014
Сообщений: 17,413
06.09.2024, 22:24
Очевидная особенность, которой можно/нужно воспользоваться:

0. Мы ищем K-тый по величине элемент воображаемой упорядоченной последовательности площадей (нумерация с нуля): K = (n+1)*(m+1)-k

1. Пусть у нас есть отсортированные по возрастанию массивы ширин ws[] и высот hs[] графств. И мы будем идти циклом по возрастанию высот.
2. Понятно, что при переходе к высоте hs[j], площадь minS = hs[j]*ws[0] будет минимальным пределом на будущее, то есть мы больше никогда не встретим площадь, меньшую чем этот minS.
3. Поэтому мы можем выбросить из рассмотрения все площади, строго меньшие этой, и уменьшить K на единицу для каждого выброшенного элемента.
4. Если в процессе выбрасывания K стало равным 0, то только что выброшенная площадь - и есть искомая.

Разумеется, крайними "плохо работающими" случаями тут будет случаи, когда hs[] имеет много одинаковых элементов. (Понятно, что hs[] и ws[] - взаимозаменяемы.)

Для борьбы с одинаковостью: на храним одинаковые площади явно, а подсчитываем количество их повторений. То есть работаем на основе std::map[площадь] = количество.
0
848 / 651 / 323
Регистрация: 24.02.2017
Сообщений: 2,297
06.09.2024, 22:34
алгоритм вычисления всех площадей на простом примере

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>     
   
int main() {
    int w, h, n, m, k;
 
    std::cin >> w >> h; // ширина и высота 3х3
    std::cin >> n >> m; // вертикальных и горизонтальных делений 2 и 2
    std::cin >> k; // сыновья
    int *x = new int[n + 2];
    int *y = new int[w + 2];
    x[0] = 0; y[0] = 0;
    x[n + 1] = w; y[m + 1] = h;
    for (int i = 1; i <= n; i++) 
        std::cin >> x[i]; // координата х[1]=1 и x[2]=2
    for (int i = 1; i <= m; i++)
        std::cin >> y[i]; // координата у[1]=1 и y[2]=2
    int *arr = new int[(n + 1)*(m + 1)]; // площадь i-того графства (в примере будет 9 площадей)
 
    for (int i = 1; i <= n + 1; i++)
        for (int j = 1; j <= m + 1; j++)
            
            std::cout <<(arr[i]= (x[i] - x[i - 1])*(y[j] - y[j - 1])) << "  ";
}
0
0 / 0 / 0
Регистрация: 05.09.2024
Сообщений: 16
06.09.2024, 23:21  [ТС]
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
hs[j], площадь minS = hs[j]*ws[0] будет минимальным пределом на будущее
Не совсем согласен. Например, длины равны hs = {7,8,10}, а ws = {5,7,9}. Тогда при j = 0 и при j = 1 minS действительно будет являться таковой, но при j = 2 будет hs[0] *ws[1] < minS.

Мне кажется, тут еще надо взаимодействовать с указателем во втором массиве, но мне не совсем понятно каким образом.
0
0 / 0 / 0
Регистрация: 05.09.2024
Сообщений: 16
06.09.2024, 23:56  [ТС]
Здравствуйте. На этот код тестирующая система выдает вердикт - ошибка выполнения. Никак не могу понять, из-за чего такое может происходить. Ошибок при работе с памятью не нашел, переполнения вроде тоже не должны происходить. (w и h не больше 10 в 9, n и m не больше 10 в 5, 1 <= k <= n*m )
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream> 
#include <algorithm> 
#include <vector> 
#define ll long long 
using namespace std;
int main() { 
    ll w, h; int n, m; ll k; 
    cin >> w >> h >> n >> m >> k;
    vector<ll> len; vector<ll> arr;
    ll last = 0; ll line;
    for (int i = 0; i < n; i++) {
        cin >> line;
        len.push_back(line - last); 
        last = line;
    }
    len.push_back(w - last);
    last = 0; 
    for (int i = 0; i <= m; i++) {
        if (i < m) cin >> line;
        else line = h;
        ll curl = line - last; 
        for (ll j : len) {
            arr.push_back(curl * j);
        }
        last = line;
    }
    sort(arr.rbegin(), arr.rend()); 
    cout << arr[k - 1] << " " << arr[0] << endl;
}
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13236 / 6868 / 1827
Регистрация: 18.10.2014
Сообщений: 17,413
07.09.2024, 07:54
Цитата Сообщение от scufford Посмотреть сообщение
Не совсем согласен. Например, длины равны hs = {7,8,10}, а ws = {5,7,9}. Тогда при j = 0 и при j = 1 minS действительно будет являться таковой, но при j = 2 будет hs[0] *ws[1] < minS.
Не понимаю, что вы имеете в виду.

Для приведенных вами данных матрица площадей будет иметь вид (ws - по горизонтали, hs - по вертикали):

50 70 90
40 56 72
35 49 63

Я веду речь лишь о том, что при проcмотре этой матрицы снизу вверх, слева направо первый элемент каждой строки - это та площадь, меньше которой мы при дальнейшем просмотре уже никогда не встретим.

Встретили 35 - далее меньше 35 мы уже не встретим. Встретили 40 - далее меньше 40 мы уже не встретим. Встретили 50 - далее меньше 50 мы уже не встретим.

---

Вот реализация, построенная на этом принципе (особо усердно не тестировал)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <cassert>
#include <vector>
#include <map>
#include <numeric>
#include <algorithm>
#include <iostream>
 
using TSizes = std::vector<unsigned>;
using TAreas = std::map<unsigned long long, unsigned>; 
 
TSizes read_sizes(unsigned n, unsigned max)
{
  TSizes szs(1 + n + 1);
  
  for (unsigned i = 1; i <= n; ++i)
  {
    std::cin >> szs[i];
    assert(szs[i - 1] < szs[i]);
  }
  
  assert(szs[n] < max);
  szs[n + 1] = max;
 
  std::adjacent_difference(szs.begin(), szs.end(), szs.begin());
  assert(szs.front() == 0);
  szs.erase(szs.begin());
  
  std::sort(szs.begin(), szs.end());
  return szs;
}
 
void add_areas(TAreas &as, unsigned h, const TSizes &ws)
{
  for (unsigned w : ws)
    ++as[(unsigned long long) w * h];
}
 
void remove_areas(TAreas &as, unsigned long long &k, unsigned long long min_a)
{
  while (k > 0 && !as.empty() && as.begin()->first < min_a)
  {
    assert(as.begin()->second > 0);
    if (as.begin()->second > k)
      k = 0;
    else
    {
      k -= as.begin()->second;
      as.erase(as.begin());
    }
  }
}
 
int main()
{
  unsigned w = 0, h = 0, n = 0, m = 0; 
  std::cin >> w >> h >> n >> m;
  assert(w > 0 && h > 0);
 
  unsigned long long k = 0;
  std::cin >> k;
  assert(k >= 1);
 
  TSizes ws = read_sizes(n, w), hs = read_sizes(m, h);
 
  ++n; ++m;
  assert(ws.size() == n && hs.size() == m);
 
  assert(k <= (unsigned long long) n * m);
  k = (unsigned long long) n * m - k; 
  // Теперь это индекс от 0 
  
  TAreas as;
  add_areas(as, hs[0], ws);
  // Начальный набор площадей
 
  for (unsigned j = 1; j < m && k > 0; ++j)
  {
    unsigned long long min_a = (unsigned long long) ws[0] * hs[j];
    // Новый гарантированный минимум
 
    // Выбрасываем площади ниже минимума
    remove_areas(as, k, min_a);
 
    // Добавляем новые площади
    add_areas(as, hs[j], ws);
  }
 
  remove_areas(as, k, -1ull);
  
  assert(!as.empty());
  std::cout << as.begin()->first << " " << (unsigned long long) ws.back() * hs.back() << std::endl;
}
Добавлено через 5 часов 53 минуты
Потестировал более усердно - все работает. Интерес представляет "подтасовка" входных данных так, чтобы заставить структуру as использовать как можно больше памяти. На случайных тестах расход все время получается мизерным.
0
0 / 0 / 0
Регистрация: 05.09.2024
Сообщений: 16
07.09.2024, 12:50  [ТС]
Добавлено через 8 минут
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Потестировал более усердно - все работает.
Все хорошо, но оно не проходит лимит по времени на одном из поздних тестов.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13236 / 6868 / 1827
Регистрация: 18.10.2014
Сообщений: 17,413
07.09.2024, 20:12
Цитата Сообщение от scufford Посмотреть сообщение
Все хорошо, но оно не проходит лимит по времени на одном из поздних тестов.
С одной стороны понятно, что вложенное итерирование по n и m - это долго. То есть нужно менять подход. Но с другой стороны есть надежда на Принцип Дирихле: чем больше величины n и m, тем мельче нарезка на графства, тем меньше разнообразие размеров графств. Поэтому в рамках "последней надежды" для данного подхода к реализации, можно попробовать применить тот же принцип std::map[размер] = количество и к хранению размеров графств, тем самым стараясь уменьшить фактические n и m

Получается даже немножко лаконичнее

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <cassert>
#include <map>
#include <iostream>
 
using TSizes = std::map<unsigned, unsigned>;
using TAreas = std::map<unsigned long long, unsigned long long>;
 
TSizes read_sizes(unsigned n, unsigned max)
{
  TSizes szs;
 
  unsigned prev_line = 0, line = 0;
  for (unsigned i = 0; i < n; ++i, prev_line = line)
  {
    std::cin >> line;
    assert(prev_line < line);
    ++szs[line - prev_line];
  }
 
  assert(prev_line < max);
  ++szs[max - prev_line];
 
  return szs;
}
 
void add_areas(TAreas& as, const TSizes::value_type &h, const TSizes& ws)
{
  for (auto &w : ws)
    as[(unsigned long long) w.first * h.first] += 
      (unsigned long long) w.second * h.second;
}
 
void remove_areas(TAreas& as, unsigned long long& k, unsigned long long min_a)
{
  while (k > 0 && !as.empty() && as.begin()->first < min_a)
  {
    assert(as.begin()->second > 0);
    if (as.begin()->second > k)
      k = 0;
    else
    {
      k -= as.begin()->second;
      as.erase(as.begin());
    }
  }
}
 
int main()
{
  unsigned w = 0, h = 0, n = 0, m = 0;
  std::cin >> w >> h >> n >> m;
  assert(w > 0 && h > 0);
 
  unsigned long long k = 0;
  std::cin >> k;
  assert(k >= 1);
 
  TSizes ws = read_sizes(n, w), hs = read_sizes(m, h);
 
  assert(k <= (unsigned long long) (n + 1) * (m + 1));
  k = (unsigned long long) (n + 1) * (m + 1) - k;
  // Теперь это индекс от 0 
 
  TAreas as;
 
  auto it_h = hs.cbegin();
  add_areas(as, *it_h, ws);
  // Начальный набор площадей
 
  for (++it_h; it_h != hs.cend(); ++it_h)
  {
    if (k == 0)
      break;
 
    unsigned long long min_a = (unsigned long long) ws.begin()->first * it_h->first;
    // Новый гарантированный минимум
 
    // Выбрасываем площади ниже минимума
    remove_areas(as, k, min_a);
 
    // Добавляем новые площади
    add_areas(as, *it_h, ws);
  }
 
  remove_areas(as, k, -1ull);
 
  assert(!as.empty());
  std::cout << 
    as.begin()->first << " " << 
    (unsigned long long) std::prev(ws.cend())->first * std::prev(hs.cend())->first << 
    std::endl;
}
Добавлено через 2 минуты
P.S. Кстати, и в предыдущей версии формально надо было бы

C++
1
using TAreas = std::map<unsigned long long, unsigned long long>;
1
0 / 0 / 0
Регистрация: 05.09.2024
Сообщений: 16
08.09.2024, 02:02  [ТС]
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Получается даже немножко лаконичнее
Увы, тоже нет. Тоже превышение лимита по времени.

GPT вот кучей сделал. Мне казалось, это не должно проходить по памяти, так как также O(k), но оно проходит тест, где возникали основные проблемы, а ломается дальше, да и то именно из-за времени.

Вообще не понимаю, как решать. Моя надежда была на map'ы, но нет.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
08.09.2024, 02:02

Ошибка выполнения цикла
Совершенно тупой вопрос... Есть простенький цикл, ошибка в 11 строке: ожидалось &quot;(&quot; перед числовой константой. Где здесь-то...

Ошибка выполнения signal 6
Происходит тут, причем вектор строк больше нигде не используется int n,m; cin&gt;&gt;n&gt;&gt;m; vector&lt;string&gt;...

Ошибка времени выполнения.
Вот код: void Add_Kod ( _kod*&amp; KodBuf, int a, char* buf, char* buf2) { if(a==1) { KodBuf = new _kod; KodBuf.ch = *(buf);...

Ошибка времени выполнения
Я пишу проэкт в Visual Studia 2008 на C++. У меня есть несколько проблем. Во-первых, когда я собираю финальную версию (release) и...

Рекурсии, ошибка выполнения
Здравствуйте, Подскажите пожалуйста в чем у меня ошибка, данный пример почему-то не работает, Спасибо #include &lt;iostream&gt; ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
39
Ответ Создать тему
Новые блоги и статьи
Вступаем в новую фазу генерации favicons, векторную.
russiannick 02.11.2026
Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .
Генератор паролей (вариант №4)
Maks 01.11.2026
После публикации 3-го варианта генератора паролей, разослал его своим коллегам (с целью оценки), в итоге были получены следующие рекомендации: 1. Вернуть возможность использования знаков | 1 l I;. . .
Генератор паролей (вариант №3)
Maks 30.10.2026
Финальная версия генератора паролей 1С. Доработка решения в этот раз коснулась только визуальной части, а именно, добавлен реквизит ДопПараметры (тип Булево), который скрывает/ отображает реквизиты:. . .
Магическое мышление и магия, современная наука не отличима от магии (говорит ИИ Джемени)
zorxor 30.10.2026
Джемени, расскажи, пожалуйста, что такое магическое мышление, что такое магия, почему современная наука чем-то напоминает магию? Фраза «Любая достаточно развитая технология неотличима от магии». . .
За какое время ИИ может подобрать пароль по хешу (рассказывает Джемени ИИ)
zorxor 30.10.2026
Расскажи, Джемени, если известен хэш МД5, например, за сколько ИИ сможет подобрать соответствующий пароль? Искусственный интеллект (ИИ) может подобрать простой или средний по сложности пароль по. . .
Кто убил Suno? Почему наше солнышко погасло? (диалог с ИИ Джемени)
zorxor 30.10.2026
Как убивали Suno. Хронология. «Убийство» музыкальной нейросети Suno — это затяжной процесс, в котором технологический хайп стартапа разбился о жесткую реальность судебных исков от гигантов. . .
Генератор паролей (вариант №2)
Maks 30.10.2026
Обновленная версия ранее созданной обработки. Добавлены следующие реквизиты типа Булево: - Буквы; - Цифры; - Символы. Изменена логика команды "Сгенерировать" и процедуры "ПриОткрытии":. . .
Генератор паролей (вариант №1)
Maks 29.10.2026
Реализация из решения ниже выполнена исключительно по моей инициативе, дабы облегчить себе работу в создании паролей для администрируемых мною сервисов и пользователей. Самым главным критерием для. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru