General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
21586001 Practice:
zhanglexing
567F - 16 GNU C++ Accepted 15 ms 1908 KB 2016-10-19 11:14:43 2016-10-19 11:14:43
→ Source
#include<cstdio>
#include<cstring>
const int N=75;
int a[N][N];//0:no 1:< 2:<= 3:= 4:>= 5:>
int n,m,i,j,x,y;
long long f[N][N];
char s[5];
bool pdl(int p,int l,int r){
	if (p<1) return 0;
	for (int i=l;i<=r;i++)
		if (a[p][i]>2) return 0;
	return 1;
}
bool pdr(int p,int l,int r){
	if (p>n) return 0;
	for (int i=l;i<=r;i++)
		if (a[p][i]>2) return 0;
	return 1;
}
int main(){
	scanf("%d%d",&n,&m);n<<=1;
	for (i=1;i<=m;i++){
		scanf("%d%s%d",&x,s,&y);
		int l=strlen(s);
		if (s[0]=='<'&&l==1) a[x][y]=1;
		if (s[0]=='<'&&l==2) a[x][y]=2;
		if (s[0]=='=') a[x][y]=3;
		if (s[0]=='>'&&l==2) a[x][y]=4;
		if (s[0]=='>'&&l==1) a[x][y]=5;
		a[y][x]=6-a[x][y];
	}
	for (i=1;i<n;i++)
		if (a[i][i+1]!=1&&a[i][i+1]!=5)
			f[i][i+1]=1;
	for (int len=2;len<=n;len+=2){
		for (i=1;i<=n-len+1;i++){
			j=i+len-1;
			bool lf1=pdl(i-1,i,j);
			bool lf2=i-2>0&&a[i-2][i-1]!=1
				&&a[i-2][i-1]!=5&&pdl(i-2,i,j);
			bool rf1=pdr(j+1,i,j);
			bool rf2=j+2<=n&&a[j+1][j+2]!=1
				&&a[j+1][j+2]!=5&&pdr(j+2,i,j);
			if (lf1&&rf1&&a[i-1][j+1]!=1&&a[i-1][j+1]!=5)
				f[i-1][j+1]+=f[i][j];
			if (lf1&&lf2) f[i-2][j]+=f[i][j];
			if (rf1&&rf2) f[i][j+2]+=f[i][j];
		}
	}
	printf("%I64d",f[1][n]);
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details