Submission #35021

#TimeUsernameProblemLanguageResultExecution timeMemory
35021itsjustwinds마스코트 (JOI13_mascots)C++11
40 / 100
13 ms73596 KiB
#include<bits/stdc++.h> #define ll long long #define maxn 55 #define mod 1000000007 using namespace std; ll gt[10000]; int a[maxn][maxn],n,r,c; ll f[maxn][maxn][maxn][maxn]; int topx,topy,downx,downy; template<typename T> inline void read(T &x) { char c; bool neg = false; while (!isdigit(c = getchar()) && c != '-'); x = 0; if (c == '-') { neg = true; c = getchar(); } do { x = x * 10 + c - '0'; } while (isdigit(c = getchar())); if (neg) x = -x; } template<typename T> inline void write(T x) { if (x < 0) { putchar('-'); write(-x); return; } if (x < 10) { putchar(char(x + 48)); } else { write(x/10); putchar(char(48 + x%10)); } } template<typename T> inline void writeln(T x) { write(x); putchar('\n'); } ll tinh(int Ux,int Uy,int Vx,int Vy) { ll res=0; if (Ux==1&&Uy==1&&Vx==r&&Vy==c) return 1; if (f[Ux][Uy][Vx][Vy]!=-1) return f[Ux][Uy][Vx][Vy]; if (Ux>1) { res=(res+(1ll*gt[Vy-Uy+1]*tinh(Ux-1,Uy,Vx,Vy))%mod)%mod; } if (Vx<r) { res=(res+(1ll*gt[Vy-Uy+1]*tinh(Ux,Uy,Vx+1,Vy))%mod)%mod; } if (Uy>1) { res=(res+(1ll*gt[Vx-Ux+1]*tinh(Ux,Uy-1,Vx,Vy))%mod)%mod; } if (Vy<c) { res=(res+(1ll*gt[Vx-Ux+1]*tinh(Ux,Uy,Vx,Vy+1))%mod)%mod; } f[Ux][Uy][Vx][Vy]=res; return res; } int main() { //freopen("Mascots.inp","r",stdin); cin.tie(0); cout.tie(0); read(r); read(c); read(n); topx=1e9,topy=1e9; for (int i=1; i<=n; ++i) { int u,v; read(u); read(v); topx=min(topx,u); topy=min(topy,v); downx=max(downx,u); downy=max(downy,v); a[u][v]=1; } gt[0]=1; for (int i=1;i<=r*c;++i) gt[i]=(gt[i-1]*i)%mod; int d=0; for (int i=topx;i<=downx;++i) for (int j=topy;j<=downy;++j) if (a[i][j]==0) ++d; memset(f,-1,sizeof f); cout<<(1ll*tinh(topx,topy,downx,downy)*gt[d])%mod; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...