У бизнесмена есть телефон, который он использует для связи с партнерами по бизнесу. Сегодня у предпринимателя запланировано n� разговоров, про каждый из которых известно число Pi�� — сколько рублей прибыли получит бизнесмен, если i�-й разговор состоится (Pi�� может быть равно 0 — в этом случае никакой выгоды от i�-го разговора нет). Телефон у бизнесмена сделан по новейшим технологиям, но иногда барахлит. Сегодня, например, телефон внезапно разрядился, поэтому он позволит бизнесмену провести только первые A0�0 разговоров, а затем выключится до конца дня. Однако телефон можно зарядить, пропустив несколько первых запланированных разговоров. Более формально, если предприниматель будет заряжать телефон вместо первых j� разговоров (то есть разговоров с номерами от 1 до j�), то он потом сможет провести ровно Aj�� разговоров (с номерами от j+1�+1 до min(n,j+Aj)(�,�+��)), после чего телефон опять же перестанет работать до конца дня. Напишите программу, которая вычислит, сколько разговоров надо пропустить бизнесмену, чтобы заработать как можно больше. Если существует несколько ответов, то выведите тот, который требует большего времени зарядки, так как бизнесмену хочется отдохнуть подольше перед звонками. Формат входных данных На вход программе дается целое число n� — количество запланированных звонков (1≤n≤2⋅1051≤�≤2⋅105). На следующей строке вводятся через пробел целые числа Pi��, обозначающие прибыли от звонков (0≤Pi≤10000≤��≤1000). Затем вводятся целые числа Aj��, обозначающие, сколько звонков можно будет провести после подзарядки (0≤Aj≤1060≤��≤106). Формат выходных данных Выведите два числа, первое — это максимальная выгода, которую может получить бизнесмен, второе — количество пропущенных первых звонков, при котором она получается (0, если выгоднее всего не заряжать телефон вовсе). Примечания Рассмотрим пример из условия: n=5�=5, P1=1�1=1, P2=2�2=2, P3=0�3=0, P4=4�4=4, P5=1�5=1, A0=2�0=2, A1=0�1=0, A2=8�2=8, A3=3�3=3, A4=5�4=5, A5=6�5=6. Если бизнесмен не будет заряжать телефон, то результат будет равен P1+P2�1+�2 = 1+21+2 = 33 рубля. Если предприниматель будет заряжать телефон вместо первого звонка, то он не сможет позвонить ни разу, так как A1=0�1=0. Если вместо первых двух звонков, то результат составит P3+P4+P5=0+4+1=5�3+�4+�5=0+4+1=5 рублей. Если вместо первых трех, то P4+P5=4+1=5�4+�5=4+1=5. Если вместо четырёх звонков, то P5=1�5=1 рубль. Наконец, если бизнесмен будет заряжать телефон вместо всех n=5�=5 звонков, то он заведомо ничего не получит. Таким образом, два лучших варианта — это заряжать либо вместо 2 первых звонков, либо вместо 3, в обоих случаях получаем 5 рублей прибыли. По условию, из них мы выбираем выбираем вариант с 3 пропущенными звонками. входные данныевыходные данные5 1 2 0 4 1 2 0 8 3 5 6 5 3
Juliyus, я могу помочь с задачей. Для решения этой задачи можно использовать два указателя, один указатель будет указывать на первый звонок, который бизнесмен может пропустить, а другой указатель будет указывать на последний звонок, который бизнесмен может сделать после зарядки телефона. Мы будем двигать эти указатели и считать сумму прибылей для каждого возможного количества пропущенных звонков. Затем выберем максимальную сумму и соответствующее количество пропущенных звонков. Вот код на C++, который решает эту задачу: #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<int> p(n); for (int i = 0; i < n; i++) { cin >> p[i]; } vector<int> a(n + 1); for (int i = 1; i <= n; i++) { cin >> a[i]; } int left = 0, right = 0; long long sum = 0, max_sum = 0; int ans = 0; while (right <= n) { if (sum > max_sum) { max_sum = sum; ans = left; } if (sum < 0) { sum = 0; left = right; } if (right - left < a[left + 1]) { sum += p[right]; right++; } else { sum -= p[left]; left++; } } cout << max_sum << " " << ans << endl; return 0; } Code #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<int> p(n); for (int i = 0; i < n; i++) { cin >> p[i]; } vector<int> a(n + 1); for (int i = 1; i <= n; i++) { cin >> a[i]; } int left = 0, right = 0; long long sum = 0, max_sum = 0; int ans = 0; while (right <= n) { if (sum > max_sum) { max_sum = sum; ans = left; } if (sum < 0) { sum = 0; left = right; } if (right - left < a[left + 1]) { sum += p[right]; right++; } else { sum -= p[left]; left++; } } cout << max_sum << " " << ans << endl; return 0; } Надеюсь, это поможет!