Решение задачи Сон на лекции с Codeforces

С пояснением   Просмотров: 100

Вы со своим другом Мишкой сидите на лекции по математическому анализу. Лекция длится n минут. Лектор рассказывает a i теорем в течение i-й минуты.

Хотя Мишке очень нравится математический анализ, иногда очень трудно не засыпать во время лекции. Вам задан массив t поведения Мишки. Если он спит в течение i-й минуты лекции, то t i равняется 0, иначе оно равняется 1. Когда Мишка не спит, он записывает все теоремы, которые слышит — a i теорем в течение i-й минуты. Иначе он не записывает ничего.

Вы знаете некоторую секретную технику, при помощи которой можно заставить не спать Мишку в течение k минут подряд. Но вы можете использовать её только один раз. Вы можете начать использовать её в любую минуту с 1 по n - k + 1. Если вы используете её в минуту i, Мишка не будет спать во все такие минуты j, что , и будет записывать все лекции, которые расскажет лектор.

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

Код 

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n, k;
	scanf("%d %d", &n, &k);
	
	vector<int> a(n);
	vector<int> t(n);
	
	int overall = 0;
	
	for (int i = 0; i < n; ++i)
		scanf("%d", &a[i]);
	for (int i = 0; i < n; ++i)
		scanf("%d", &t[i]);
		
	vector<int> pr(n);
	for (int i = 0; i < n; ++i) {
		if (i) pr[i] += pr[i - 1];
		if (t[i] == 0) pr[i] += a[i];
		else overall += a[i];
	}
	
	int add = 0;
	for (int i = k - 1; i < n; ++i)
		add = max(add, pr[i] - (i >= k ? pr[i - k] : 0));
	
	printf("%d\n", overall + add);
	
	return 0;
}

         

Администратор Photo Автор: Администратор


Пояснение к задаче

Проитерируемся по всем i от 1 до n, и если t i равняется 1, тогда добавим a i к некоторой переменной res и заменим a i на 0. Тогда ответ будет равен , где можно легко посчитать при помощи префиксных сумм для всех i.



Комментарии

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


© 2020 HSECODES [email protected] Карта сайта