General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
12917082 Practice:
zyf940104357
567F - 15 GNU C++ Accepted 31 ms 51656 KB 2015-09-10 05:33:22 2015-09-10 05:33:23
→ Source
#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
const int maxn=2015,maxk=100010;
bool t[maxn][maxn]; int s[maxn][maxn];
int n,k;

inline int get(int x1,int y1,int x2,int y2){
    return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
}
void init(){
    memset(t,false,sizeof(t));
    memset(s,0,sizeof(s));
    for(int i=1;i<=k;++i){
        int u,v; char str[5];
        scanf("%d%s%d",&u,str,&v);
        if(str[0]=='>') swap(u,v),str[0]='<';
        ++s[u][v];
        if(str[0]=='=') ++s[v][u];
        else if(!str[1]) t[u][v]=true;
    }
    for(int i=1;i<=(n<<1);++i)
        for(int j=1;j<=(n<<1);++j)
            s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}

int64 f[maxn][maxn];
void dp(){
    memset(f,0,sizeof(f));
    for(int i=1;i<=(n<<1)-1;++i)
        f[n][i]=!t[i][i+1] && !t[i+1][i];
    for(int i=n-1;i>=1;--i){
        for(int l=1,r=(n-i+1)<<1;r<=(n<<1);++l,++r){
            if(!t[l][r] && !t[r][l] && !get(l+1,l,r-1,l) && !get(l+1,r,r-1,r))
                f[i][l]+=f[i+1][l+1];
            if(!t[l][l+1] && !t[l+1][l] && !get(l+2,l,r,l+1))
                f[i][l]+=f[i+1][l+2];
            if(!t[r-1][r] && !t[r][r-1] && !get(l,r-1,r-2,r))
                f[i][l]+=f[i+1][l];
        }
    }
    cout<<f[1][1]<<endl;
}

int main(){
    while(scanf("%d%d",&n,&k)!=EOF)
        init(),dp();
    return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details