Нужно оптимизировать код

@Bluestick · Регистрация: 15.07.2019

Студворк — интернет-сервис помощи студентам

Гистограмма является многоугольником, сформированным из последовательности прямоугольников, выровненных на общей базовой линии. Прямоугольники имеют равную ширину, но могут иметь различные высоты. Например, фигура слева показывает гистограмму, которая состоит из прямоугольников с высотами 2, 1, 4, 5, 1, 3, 3.
Обычно гистограммы используются для представления дискретных распределений, например, частоты символов в текстах. Отметьте, что порядок прямоугольников очень важен. Вычислите область самого большого прямоугольника в гистограмме, который также находится на общей базовой линии.

Входные данные
В первой строке входного файла записано число N (0 < N ≤ 10^6) - количество прямоугольников гистограммы. Затем следует N целых чисел h^1 h^n, где 0 ≤ h^i ≤ 10^9. Эти числа обозначают высоты прямоугольников гистограммы слева направо. Ширина каждого прямоугольника равна 1

Выходные данные
Выведите площадь самого большого прямоугольника в гистограмме. Помните, что этот прямоугольник должен быть на общей базовой линии.

Примеры
входные данные
7 2 1 4 5 1 3 3
выходные данные
8
Есть код, но не проходит 1 тест по времени (ограничение 1 сек. у меня этот тест проходит за 1.096)

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
#include <stdio.h>
 
#define MAX 1000010
 
 
 
long long h[MAX];
 
int i, n, left, right;
 
long long area, res;
 
 
 
int main(void)
 
{
 
  scanf("%d",&n);
 
  for(i = 1; i <= n; i++)
 
    scanf("%d",&h[i]);
 
 
 
  res = 0;
 
  for(i = 1; i <= n; i++)
 
  {
 
    left = right = i;
 
    while(left > 1 && h[left-1] >= h[i]) left--;
 
    while(right < n && h[right+1] >= h[i]) right++;
 
    area = (right - left + 1) * h[i];
 
    if (area > res) res = area;
 
  }
 
  printf("%lld\n",res);
 
  return 0;
 
}

Реализация за O(n2) если что
Я эту тему уже создавал, но создал не в С++ для начинающих, а просто с++ поэтому решил тут сделать, а удалить не могу

@Pvt · 30.07.2019, 08:54

ссылка где проверяют?

@Bluestick · 30.07.2019, 09:06 **[ТС]**

https://informatics.mccme.ru/m... d=113915#1

@kitsoRik · 30.07.2019, 09:11

Bluestick, в данном случае, площать самого большого прямоугольника, это у прямоугольника у которого самая большая высота, что за базовая линия?

Добавлено через 3 минуты

Сообщение от Bluestick

Примеры
входные данные
7 2 1 4 5 1 3 3
выходные данные
8

Почему тут 8? Разве 7*1 не будет 7?

@Bluestick · 30.07.2019, 09:20 **[ТС]**

с чего вы взяли что 7? Прямоугольник должен быть на общей базовой черте
(в ссылке есть задача Гистограмма, а в ней рисунок как только посмотрите поймете)

@XLAT · 30.07.2019, 09:24

Сообщение от kitsoRik

Почему тут 8? Разве 7*1 не будет 7?

Сообщение от Bluestick

В первой строке входного файла записано число N (0 < N ≤ 10^6) - количество прямоугольников гистограммы.

7 это кол-во прямоугольников.
ответ должен быть 5.

Добавлено через 2 минуты

Сообщение от Bluestick

в ссылке есть задача Гистограмма

Сообщение от Bluestick

https://informatics.mccme.ru/mod/sta...terid=113915#1

это реклама?
чтобы 2 секунды посмотреть на вашу гистограмму мне надо 20 минут потратить на регистрацию?

@kitsoRik · 30.07.2019, 09:24

Bluestick, там вход по кодовому слову

Сообщение от XLAT

7 это кол-во прямоугольников.
ответ должен быть 5.

тут да, незаметил, всегда же делают перевод что бы отделить, хорошо, но ответ то не совпал

@Bluestick · 30.07.2019, 09:25 **[ТС]**

ну смотрите, 7 - это просто столб (т.к у него ширина 1, а нам нужен прямоугольник) рядом с ним стоит столб в высотой 2 и получается прямоугольник 2 на 2. Это и есть базовая черта
Попробуйте в paint нарисован примерно и тогда поймете

@Pvt · 30.07.2019, 09:27

региться еще по этой ссылке, сами проверяйте

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
int h[1000000]={7, 2, 1, 4, 5, 1, 3, 3};
void main(int argc,char **argv)
{
    int n=8;
    scanf("%d",&n);
    for(int i = 0; i < n; i++)
        scanf("%d",h+i);
    int left, right, old;
    long long area, res=0;
    for(int i = 0; i < n; i++)
    {
        left = right = i;
        int hi=h[i];
        if(i)
        {
            if(hi==h[i-1]) continue;
            if(hi<h[i-1]) left=old;
        }
        while(left && h[left-1] >= hi) left--;
        while(right < n-1 && h[right+1] >= hi) right++;
        area = (right - left + 1ll) * hi;
        if (area > res) res = area;
        old=left;
    }
    cout<<res<<endl;

@Bluestick · 30.07.2019, 09:27 **[ТС]**

главное понимать что нам нужны именно прямоугольники, а не столбы

@kitsoRik · 30.07.2019, 09:27

Bluestick, Гистограмма

Сообщение от Bluestick

это просто столб (т.к у него ширина 1, а нам нужен прямоугольник)

столб не прямоугольник? У него в любом случае есть высота и ширина,

Сообщение от Bluestick

2 на 2

2 на 2? Так ширина же всегда 1.

@Bluestick · 30.07.2019, 09:35 **[ТС]**

Они соединяются столбы что дают во входных прилипают друг к другу от того и получается что

Сообщение от Bluestick

4 5

ихняя площадь больше чем площадь 5

Добавлено через 39 секунд
ошибка компиляции
(в начале коде я добавлял #include <iostream> using namespace std; так что не из-за этого)

@XLAT · 30.07.2019, 09:40

Сообщение от Bluestick

Попробуйте в paint нарисован примерно и тогда поймете

всё по инструкции:

Сообщение от Bluestick

ну смотрите, 7 - это просто столб (т.к у него ширина 1, а нам нужен прямоугольник) рядом с ним стоит столб в высотой 2 и получается прямоугольник 2 на 2. Это и есть базовая черта

прямоугольник 2 на 2 является чертой?

@Bluestick · 30.07.2019, 09:41 **[ТС]**

именно так

@Pvt · 30.07.2019, 09:43

Сообщение от Bluestick

ошибка компиляции

main закрыт }?

@Bluestick · 30.07.2019, 10:09 **[ТС]**

Сообщение от Pvt

void main(int argc,char **argv)

про это? Если закрою хуже станет

@Pvt · 30.07.2019, 10:16

..... стр.26 = }

@Bluestick · 30.07.2019, 12:13 **[ТС]**

что значит стр 26?

@kitsoRik · 30.07.2019, 12:41

Сообщение от Bluestick

что значит стр 26?

строка

@Bluestick · 30.07.2019, 13:38 **[ТС]**

005215.cpp:4:32: error: '::main' must return 'int'
void main(int argc, char **argv)
видимо ошибка на уровне входных данных
(я не могу запустить код, ибо с++ недавно сломался и не хочет запускать коды)

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .

@Pvt Заблокирован
	30.07.2019, 08:54
	ссылка где проверяют? 0

@Bluestick 0 / 0 / 0 Регистрация: 15.07.2019 Сообщений: 69
	30.07.2019, 09:06 [ТС]
	https://informatics.mccme.ru/m... d=113915#1 0

@Bluestick 0 / 0 / 0 Регистрация: 15.07.2019 Сообщений: 69
	30.07.2019, 09:20 [ТС]
	с чего вы взяли что 7? Прямоугольник должен быть на общей базовой черте (в ссылке есть задача Гистограмма, а в ней рисунок как только посмотрите поймете) 0

@Bluestick 0 / 0 / 0 Регистрация: 15.07.2019 Сообщений: 69
	30.07.2019, 09:25 [ТС]
	ну смотрите, 7 - это просто столб (т.к у него ширина 1, а нам нужен прямоугольник) рядом с ним стоит столб в высотой 2 и получается прямоугольник 2 на 2. Это и есть базовая черта Попробуйте в paint нарисован примерно и тогда поймете 0

@Bluestick 0 / 0 / 0 Регистрация: 15.07.2019 Сообщений: 69
	30.07.2019, 09:27 [ТС]
	главное понимать что нам нужны именно прямоугольники, а не столбы 0

@Bluestick 0 / 0 / 0 Регистрация: 15.07.2019 Сообщений: 69
	30.07.2019, 09:41 [ТС]
	именно так 0

@Pvt Заблокирован
	30.07.2019, 10:16
	..... стр.26 = } 0

@Bluestick 0 / 0 / 0 Регистрация: 15.07.2019 Сообщений: 69
	30.07.2019, 12:13 [ТС]
	что значит стр 26? 0

@Bluestick 0 / 0 / 0 Регистрация: 15.07.2019 Сообщений: 69
	30.07.2019, 13:38 [ТС]
	005215.cpp:4:32: error: '::main' must return 'int' void main(int argc, char **argv) видимо ошибка на уровне входных данных (я не могу запустить код, ибо с++ недавно сломался и не хочет запускать коды) 0