Защищенный пароль

[Poma][a]

А можно в 3-х словах идею?

[Аватар]

В трех словах слабо. Читаю символы и заполняю частотный массив. Как только больше k раз встретился один из символов левый символ убираю их прочитанного. До тех пор пока не уберется символ, который встретился больше k раз. Все сопровождается наращиванием счетчика подстрок. В хреновом случае, например n=k=1000000 и вся строка из одного символа, все 1000000 символов одновременно будут считаны в память

[Poma][a]

Пан Аватар, а не подскажете, что там за хитрющий 17 тест?

[Аватар]

А их можно подсмотреть? Понятия не имею как

[Poma][a]

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

[Аватар]

А, что-то было. И вроде здесь:

if j>k then Inc(m,((j-k+1)*(j-k)) div 2);

для этого и сделал не только n int64, но и k. Похоже (j-k+1)*(j-k) выскакивало за пределы longint. В принципе n можно было и не делать таким типом, но сделал его в начале из-за

m:=((2*n-k+1)*k) div 2;

и благополучно забыл про это. k было бы достаточно

[Poma][a]

Спасибо!
Похимичил с типами, чтобы зашло..
Вот мой вариант :

#include <fstream>
#include <vector>
#include <queue>
#include <map>

using namespace std;

map<char, queue<int> > p;

int main()
{
	ifstream cin("input.txt");
	ofstream cout("output.txt");

	long long n, k;
	char ch;
	cin >> n >> k >> ch;

	vector<long long> a(n);
	a[0] = 1;
	p[ch].push(0);

	long long j = 0;
	for (long long i = 1; i < n; i++)
	{
		cin >> ch;
		p[ch].push(i);
		if (p[ch].size() > k)
		{
			if (j < p[ch].front() + 1)
				j = p[ch].front()+1;
			p[ch].pop();
		}
		a[i] = i-j + 1 + a[i-1];
	}
	cout << a[n-1];
	return 0;
}

[Аватар]

Памяти сколько использовал?

[Poma][a]

14 мб
Я очень много 10^6*2 на хранение всей необходимой (наверное) инфы, для быстрого нахождения j

UPDATE
Уже 6.2

#include <fstream>
#include <vector>
#include <queue>
#include <map>

using namespace std;

map<char, queue<int> > p;

int main()
{
	ifstream cin("input.txt");
	ofstream cout("output.txt");

	long long n, k;
	char ch;
	cin >> n >> k >> ch;

	long long v = 1;
	p[ch].push(0);

	long long j = 0;
	for (long long i = 1; i < n; i++)
	{
		cin >> ch;
		p[ch].push(i);
		if (p[ch].size() > k)
		{
			if (j < p[ch].front() + 1)
				j = p[ch].front()+1;
			p[ch].pop();
		}
		v += i - j + 1;
	}
	cout << v;
	return 0;
}

[Аватар]

Ясненько, не ахти. Придумай 60Кб. Там школяры (или не?) придумали