oj.uz

Submission #35021

# Submission time Handle Problem Language Result Execution time Memory
35021 2017-11-17T10:12:04 Z itsjustwinds 마스코트 (JOI13_mascots) C++11
40 / 100
 13 ms 73596 KB 
#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;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 73596 KB Output is correct
2 Correct 6 ms 73596 KB Output is correct
3 Correct 6 ms 73596 KB Output is correct
4 Correct 0 ms 73596 KB Output is correct
5 Correct 6 ms 73596 KB Output is correct
6 Correct 0 ms 73596 KB Output is correct
7 Correct 6 ms 73596 KB Output is correct
8 Correct 13 ms 73596 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 73596 KB Output is correct
2 Correct 6 ms 73596 KB Output is correct
3 Correct 0 ms 73596 KB Output is correct
4 Correct 6 ms 73596 KB Output is correct
5 Correct 9 ms 73596 KB Output is correct
6 Correct 3 ms 73596 KB Output is correct
7 Correct 3 ms 73596 KB Output is correct
8 Correct 9 ms 73596 KB Output is correct
9 Correct 9 ms 73596 KB Output is correct
10 Correct 9 ms 73596 KB Output is correct
11 Correct 6 ms 73596 KB Output is correct
12 Correct 13 ms 73596 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 73596 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -