oj.uz

답안 #855123

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
855123 2023-09-30T08:18:57 Z clams Difference (POI11_roz) C++17
100 / 100
 178 ms 5444 KB 
/*************************************************************************
 *                                                                       *
 *                    XVIII Olimpiada Informatyczna                      *
 *                                                                       *
 *   Zadanie:           Roznica                                          *
 *   Autor:             Zbigniew Wojna                                   *
 *   Zlozonosc czasowa: O(n * k)                                         *
 *   Opis:              Rozwiazanie wzorcowe                             *
 *                      Badamy od poczatku i konca mozliwe slowa         *
 *                      dynamicznie uaktualniajac liczbe liter           *
 *                      ktore sie pojawily i mialy sens                  *
 *                                                                       *
 *************************************************************************/

#include <cstdio>
#include <vector>
#include <set>
#include <iostream>

using namespace std;

#define REP(i,n) for(int _n=n, i=0;i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
#define FORE(i,x) for(__typeof((x).begin()) i=(x).begin();i != (x).end();++i)
#define X first
#define Y second
#define PB push_back	
#define MP make_pair
#define MAXN 1000005		

int slowo[MAXN];		// tablica z wczytanym slowem
int licznik[26];		// tymczasowa tablica trzymajaca liczby poszczegolnych liter
bool ok[26];			// prawda oznacza ze potrzebujemy jeszcze dodatkowej litery 
						// na poczatku lub na koncu segmentu zlozonego z badanej litery
int n, temp, licz, maks;
char c;


int main()
{
	// wczytanie slowa i przesuniecie
	temp = scanf("%d", &n);
	temp = scanf("%c", &c);
	REP(i, n) 
	{
		temp = scanf("%c", &c);
		slowo[i] = c - 97;
	}	

	// wyliczamy najlepszy fragment dla kazdej litery 
	REP(i, 26)
	{
		
		// czyszczenie
		REP(j, 26)
		{
			ok[j] = false;
			licznik[j] = 0;
		}
		licz = 0;

		// petla po slowie od poczatku, gdy trafimy na badana litere zwiekszamy
		// jej liczbe i sprawdzamy czy max sie poprawil
		// w drugim przypadku zwiekszamy liczbe innej litery o ile ma to sens
		REP(j, n)
			if(slowo[j] == i)
			{
				licz++;
				REP(k, 26)
					if(licz - licznik[k] > maks && licznik[k] > 0)
							maks = max(maks, licz - licznik[k]);
			}
			else
			{
				if(licznik[slowo[j]] < licz + 1)
					licznik[slowo[j]]++;
				if(licznik[slowo[j]] > licz)
					ok[slowo[j]] = true;
				else
					if(ok[slowo[j]] == true)
					{
						ok[slowo[j]] = false;
						licznik[slowo[j]]--;
						maks = max(maks, licz - licznik[slowo[j]]);
					}
			}

		// czyszczenie
		REP(j, 26)
		{
			ok[j] = false;
			licznik[j] = 0;
		}
		licz = 0;

		// petla po slowie od konca
		FORD(j, n - 1, 0)
			if(slowo[j] == i)
			{
				licz++;
				REP(k, 26)
					if(licz - licznik[k] > maks && licznik[k] > 0)
							maks = max(maks, licz - licznik[k]);
			}
			else
			{
				if(licznik[slowo[j]] < licz + 1)
					licznik[slowo[j]]++;
				if(licznik[slowo[j]] > licz)
					ok[slowo[j]] = true;
				else
					if(ok[slowo[j]] == true)
					{
						ok[slowo[j]] = false;
						licznik[slowo[j]]--;
						maks = max(maks, licz - licznik[slowo[j]]);
					}
			}

		
	}


	// wypisanie wyniku
	printf("%d\n", maks);

	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 452 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 2908 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 5304 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 136 ms 4424 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 172 ms 5196 KB Output is correct
2 Correct 134 ms 4312 KB Output is correct
3 Correct 139 ms 4804 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 175 ms 5208 KB Output is correct
2 Correct 152 ms 5308 KB Output is correct
3 Correct 146 ms 5304 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 178 ms 5304 KB Output is correct
2 Correct 137 ms 5200 KB Output is correct
3 Correct 166 ms 5444 KB Output is correct