Submission #1319089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319089		neonglitch	DEL13 (info1cup18_del13)	C++20	22 / 100	853 ms	1592 KiB

del13

#include <iostream>
using namespace std;
const int N=2e5+10;
int a[N],gap[N];
bool dp[N][200];
void solve()
{
	int n,k;
	cin>>n>>k;
	a[0]=0;
	for(int i=1;i<=k+1;i++)
	{
		if(i<=k)
			cin>>a[i];
		else{
			a[i]=n+1;
		}
		gap[i]=a[i]-a[i-1]-1;
	}
	// gap[i]<=2
	for(int i=0;i<=k+1;i++)for(int j=0;j<=n+1;j++)dp[i][j]=0;
	dp[1][gap[1]]=1;
	for(int i=1;i<=k+1;i++)
	{
		for(int j=n+1;j>=3;j--)
			dp[i][j-2]|=dp[i][j];
		for(int j=0;j<=n+1;j++)
		{
			if(j<=gap[i+1])
			{
				for(int k1=gap[i+1];j<=k1;)
				{
					dp[i+1][k1-j]|=dp[i][j];
					if(k1>2)k1-=2;
					else break;
				}
			}
		}
	}
	int r=-1;
	if(dp[k+1][0])r=0;
	cout<<r<<endl;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}

}

• Subtask 1: 6 / 15
• Subtask 2: 6 / 15
• Subtask 3: 0 / 15
• Subtask 4: 10 / 25
• Subtask 5: 0 / 30