Submission #3044858


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef int sign;
typedef long long ll;
#define For(i,a,b) for(register sign i=(sign)(a);i<=(sign)(b);++i)
#define Fordown(i,a,b) for(register sign i=(sign)(a);i>=(sign)(b);--i)
const int N=20+5;
template<typename T>bool cmax(T &a,T b){return (a<b)?a=b,1:0;}
template<typename T>bool cmin(T &a,T b){return (a>b)?a=b,1:0;}
template<typename T>T read()
{
	T ans=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)&&ch!='-')ch=getchar();
	if(ch=='-')f=-1,ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch-'0'),ch=getchar();
	return ans*f;
}
template<typename T>void write(T x,char y)
{
	if(x==0)
	{
		putchar('0'),putchar(y);
		return;
	}
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	static char wr[20];
	int top=0;
	for(;x;x/=10)wr[++top]=x%10+'0';
	while(top)putchar(wr[top--]);
	putchar(y);
}
void file()
{
#ifndef ONLINE_JUDGE
	freopen("F.in","r",stdin);
	freopen("F.out","w",stdout);
#endif
}
int n,m,k;
int limit[N][N];
void input()
{
	int x,y,z;
	n=read<int>()-1,m=read<int>(),k=read<int>();
	memset(limit,-1,sizeof limit);
	For(i,1,k)
	{
		x=read<int>(),y=read<int>(),z=read<int>();
		limit[x][y]=z;
	}
}
const int mo=1e9+7;
int dp[2][20][1<<19];
void add(int &x,int y)
{
	x+=y;x-=(x>=mo?mo:0);
}
void work()
{
	int now=1,pre=0;
	dp[0][n][0]=1;
	int Max=(1<<n)-1;
	For(i,1,m)
	{
		memset(dp[now],0,sizeof dp[now]);
		For(s,0,Max)dp[now][0][s]=dp[pre][n][s];
		For(j,1,n)For(s,0,Max)if(dp[now][j-1][s])
		{
			int o=(s>>(j-1))&1;
			if(limit[i][j]==0&&o==1)continue;
			if(limit[i][j]==-1||(limit[i][j]==o))add(dp[now][j][s],dp[now][j-1][s]);
			if(o==0&&limit[i][j]!=0)
			{
				int nex=s|(1<<(j-1));
				For(l,j+1,n)if(((nex>>(l-1)))&1){nex^=(1<<(l-1));break;}
				add(dp[now][j][nex],dp[now][j-1][s]);
			}
		}
		swap(now,pre);
	}
	int ans=0;
	For(i,0,Max)add(ans,dp[pre][n][i]);//,cerr<<i<<' '<<dp[pre][n][i]<<endl;
	write(ans,'\n');
}
int main()
{
	//file();
	input();
	work();
	//cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
	return 0;
}

Submission Info

Submission Time
Task F - Zigzag
User dengyixuan
Language C++14 (GCC 5.4.1)
Score 1600
Code Size 2082 Byte
Status AC
Exec Time 1250 ms
Memory 82176 KB

Compile Error

./Main.cpp: In function ‘void file()’:
./Main.cpp:40:27: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
  freopen("F.in","r",stdin);
                           ^
./Main.cpp:41:29: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
  freopen("F.out","w",stdout);
                             ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1600 / 1600
Status
AC × 4
AC × 41
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt, sample4.txt
All sample1.txt, sample2.txt, sample3.txt, sample4.txt, a1.txt, a10.txt, a11.txt, a12.txt, a13.txt, a2.txt, a3.txt, a4.txt, a5.txt, a6.txt, a7.txt, a8.txt, a9.txt, b1.txt, b10.txt, b11.txt, b12.txt, b13.txt, b14.txt, b15.txt, b16.txt, b17.txt, b2.txt, b3.txt, b4.txt, b5.txt, b6.txt, b7.txt, b8.txt, b9.txt, n18.txt, n19.txt, n20.txt, sample1.txt, sample2.txt, sample3.txt, sample4.txt
Case Name Status Exec Time Memory
a1.txt AC 47 ms 82176 KB
a10.txt AC 652 ms 82176 KB
a11.txt AC 471 ms 82176 KB
a12.txt AC 425 ms 82176 KB
a13.txt AC 420 ms 82176 KB
a2.txt AC 47 ms 82176 KB
a3.txt AC 47 ms 82176 KB
a4.txt AC 78 ms 82176 KB
a5.txt AC 123 ms 82176 KB
a6.txt AC 1225 ms 82176 KB
a7.txt AC 1026 ms 82176 KB
a8.txt AC 1032 ms 82176 KB
a9.txt AC 842 ms 82176 KB
b1.txt AC 138 ms 82176 KB
b10.txt AC 794 ms 82176 KB
b11.txt AC 503 ms 82176 KB
b12.txt AC 361 ms 82176 KB
b13.txt AC 319 ms 82176 KB
b14.txt AC 287 ms 82176 KB
b15.txt AC 284 ms 82176 KB
b16.txt AC 284 ms 82176 KB
b17.txt AC 284 ms 82176 KB
b2.txt AC 459 ms 82176 KB
b3.txt AC 132 ms 82176 KB
b4.txt AC 49 ms 82176 KB
b5.txt AC 138 ms 82176 KB
b6.txt AC 60 ms 82176 KB
b7.txt AC 1223 ms 82176 KB
b8.txt AC 1134 ms 82176 KB
b9.txt AC 974 ms 82176 KB
n18.txt AC 350 ms 82176 KB
n19.txt AC 631 ms 82176 KB
n20.txt AC 1249 ms 82176 KB
sample1.txt AC 29 ms 82176 KB
sample2.txt AC 29 ms 82176 KB
sample3.txt AC 41 ms 82176 KB
sample4.txt AC 1250 ms 82176 KB