8802022-01-25 09:19:20kidesoDNScpp11Időlimit túllépés 12/40398ms25076 KiB
#include <iostream>
#include <vector>
#include <string>

using namespace std;

string s;
vector <vector<int>> x;
int N;

bool check(int k) {

	for (int l = 0; l < 4; ++l)
		if (2 * x[k - 1][l] >= k) return true;

	for (int i = 1; i < N - k; ++i)
		for (int l = 0; l < 4; ++l)
			if (2 * (x[i + k][l] - x[i - 1][l]) >= k) return true;

	return false;
}

int megold(int b, int j) {
	if (b == j) return b;
	int k = (b + j) / 2;
	if (check(k)) return megold(k, j);
	else return megold(b, k-1);
}


int main()
{
	cin >> s;
	N = s.length();
	x.resize(N, vector<int>(4, 0));

	for (int i = 0; i < N; ++i) {
		if (i > 0) x[i] = x[i - 1];
		if (s[i] == 'A') ++x[i][0];
		else if (s[i] == 'C') ++x[i][1];
		else if (s[i] == 'G') ++x[i][2];
		else ++x[i][3];
	}

	cout << megold(1, N);

	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base12/40
1Elfogadva0/02ms1744 KiB
2Időlimit túllépés0/0389ms12272 KiB
3Elfogadva2/21ms2036 KiB
4Elfogadva2/21ms2044 KiB
5Időlimit túllépés0/2393ms1096 KiB
6Időlimit túllépés0/2393ms1200 KiB
7Hibás válasz0/21ms2108 KiB
8Időlimit túllépés0/4398ms4020 KiB
9Elfogadva4/412ms10892 KiB
10Hibás válasz0/416ms13192 KiB
11Elfogadva4/418ms16704 KiB
12Hibás válasz0/419ms19036 KiB
13Hibás válasz0/526ms22704 KiB
14Hibás válasz0/528ms25076 KiB