№ |
Отправитель |
Задача |
Язык |
Вердикт |
Время |
Память |
Отослано |
Протест. |
|
57885006 |
Дорешивание:
lopare |
567F
- 16
|
GNU C++11
|
Полное решение
|
31 мс
|
84 КБ
|
2019-07-28 12:27:02 |
2019-07-28 12:28:39 |
|
#include<bits/stdc++.h>
using namespace std;
long long f[80][80];
int opt[80][80];
int main()
{
int i,n,k,j,x,y,c,d,l;
char s[4];
scanf("%d%d",&n,&k);
for(i=1;i<=k;i++)
{
scanf("%d%s%d",&x,s,&y);
switch(s[0])
{
case '=':
c=1;d=1;break;
case '<':
if(s[1])
{c=2;d=8;}
else
{c=4;d=16;}break;
case '>':
if(s[1])
{c=8;d=2;}
else
{c=16;d=4;}break;
}
opt[x][y]|=c;
opt[y][x]|=d;
if(x==y&&(c&11)==0)
{
printf("%d",0);
return 0;
}
}
for(i=1;i<2*n;i++)
if((opt[i][i+1]&20)==0)
f[i][i+1]=1;
for(i=2*n;i>=1;i--)
for(j=i+3;j<=2*n;j+=2)
{
c=0;
for(l=i;l<=j-2;l++)
c|=opt[l][j-1]|opt[l][j];
if((opt[j-1][j]&20)==0&&(c&7)==0)
f[i][j]+=f[i][j-2];
c=0;
for(l=i+2;l<=j;l++)
c|=opt[i][l]|opt[i+1][l];
if((opt[i][i+1]&20)==0&&(c&25)==0)
f[i][j]+=f[i+2][j];
c=0;d=0;
for(l=i+1;l<=j-1;l++)
{
c|=opt[i][l];
d|=opt[l][j];
}
if((opt[i][j]&20)==0&&(c&25)==0&&(d&7)==0)
f[i][j]+=f[i+1][j-1];
}
printf("%I64d",f[1][2*n]);
return 0;
}
Время: ? ms, память: ? КБ