Submission #625419

#	Time	Username	Problem	Language	Result	Execution time	Memory
625419		Augustyn	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	8 ms	3036 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
int n,k,odp=INT_MAX,ile[3],gdzie[3],pref[200001][3];
char ciag[200001];
int main()
{
	scanf("%d%d",&n,&k);
	char wcz=getchar();
	while(wcz!='J'&&wcz!='O'&&wcz!='I')
		wcz=getchar();
	for(int i=1;i<=n;++i)
	{
		ciag[i]=wcz;
		for(int j=0;j<3;++j)
			pref[i][j]=pref[i-1][j];
		if(ciag[i]=='J')
			++pref[i][0];
		else if(ciag[i]=='O')
			++pref[i][1];
		else
			++pref[i][2];
		wcz=getchar();
	}
	while(ile[0]<k)
	{
		++gdzie[0];
		if(gdzie[0]>n)
		{
			printf("-1");
			return 0;
		}
		if(ciag[gdzie[0]]=='J')
			++ile[0];
	}
	gdzie[1]=gdzie[0];
	while(ile[1]<k)
	{
		++gdzie[1];
		if(gdzie[1]>n)
		{
			printf("-1");
			return 0;
		}
		if(ciag[gdzie[1]]=='O')
			++ile[1];
	}
	gdzie[2]=gdzie[1];
	while(ile[2]<k)
	{
		++gdzie[2];
		if(gdzie[2]>n)
		{
			printf("-1");
			return 0;
		}
		if(ciag[gdzie[2]]=='I')
			++ile[2];
	}
	odp=gdzie[2]-3*k;
	for(int i=2;i<=n;++i)
	{
		if(ciag[i-1]=='J')
		{
			int gpam=gdzie[0];
			--ile[0];
			while(ile[0]<k)
			{
				++gdzie[0];
				if(gdzie[0]>n)
				{
					printf("%d",odp);
					return 0;
				}
				if(ciag[gdzie[0]]=='J')
					++ile[0];
			}
			if(gdzie[0]>gdzie[1])
			{
				gdzie[1]=gdzie[0];
				ile[1]=0;
			}
			else
			{
				ile[1]-=pref[gdzie[0]][1]-pref[gpam][1];
			}


			gpam=gdzie[1];
			while(ile[1]<k)
			{
				++gdzie[1];
				if(gdzie[1]>n)
				{
					printf("%d",odp);
					return 0;
				}
				if(ciag[gdzie[1]]=='O')
					++ile[1];
			}
			if(gdzie[1]>gdzie[2])
			{
				gdzie[2]=gdzie[1];
				ile[2]=0;
			}
			else
			{
				ile[2]-=pref[gdzie[1]][2]-pref[gpam][2];
			}

			while(ile[2]<k)
			{
				++gdzie[2];
				if(gdzie[2]>n)
				{
					printf("%d",odp);
					return 0;
				}
				if(ciag[gdzie[2]]=='I')
					++ile[2];
			}
		}
		odp=min(odp,gdzie[2]-i+1-3*k);
	}
	printf("%d",odp);
	return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:7:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |  scanf("%d%d",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 12 / 12
• Subtask 3: 87 / 87