oj.uz

Submission #45299

# Submission time Handle Problem Language Result Execution time Memory
45299 2018-04-12T17:47:18 Z Extazy Tents (JOI18_tents) C++17
100 / 100
 1573 ms 42784 KB 
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 3007;
const int MOD = (1e9) + 7;

int n,m;
bool used[N][N];
int state[N][N];

int choose(int n, int k) {
    if(k==0) return 1;
    if(k==1) return n;
    return n*(n-1)/2;
}

int ways(int k) {
    if(k==0) return 1;
    if(k==1) return 4;
    return 1;
}

int recurse(int n, int m) {
    if(n==0 || m==0) return 1;

    if(used[n][m]) return state[n][m];
    
    long long ans=0;

    //1) There is a tent in (1,1) and no other tents in row 1 or column 1
    ans+=4ll*recurse(n-1,m-1);

    //2) There is a tent in (1,1) and a tent in (1,x)
    if(m>=2) ans+=(m-1)*1ll*recurse(n-1,m-2);

    //3) There is a tent in (1,1) and a tent in (x,1)
    if(n>=2) ans+=(n-1)*1ll*recurse(n-2,m-1);

    int row,col;

    for(row=0;row<=2 && row+1<=n;row++) {
        for(col=0;col<=2 && col+1<=m;col++) {
            ans+=choose(n-1,row)*1ll*choose(m-1,col)*ways(row)*ways(col)%MOD*recurse(n-1-row,m-1-col);
            
            int rows_left=n-1-row,cols_left=m-1-col;

            if(row==1 && cols_left>=1) ans+=choose(n-1,row)*1ll*choose(m-1,col)*cols_left*ways(col)%MOD*recurse(rows_left,cols_left-1);
            if(col==1 && rows_left>=1) ans+=choose(n-1,row)*1ll*choose(m-1,col)*ways(row)*rows_left%MOD*recurse(rows_left-1,cols_left);
            if(row==1 && col==1 && rows_left>=1 && cols_left>=1) ans+=choose(n-1,row)*1ll*choose(m-1,col)*rows_left*cols_left%MOD*recurse(rows_left-1,cols_left-1);
        }
    }

    used[n][m]=true;
    return state[n][m]=ans%MOD;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    scanf("%d %d", &n, &m);
    printf("%d\n", (recurse(n,m)-1+MOD)%MOD);
    
    return 0;
}

Compilation message

tents.cpp: In function 'int main()':
tents.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 5 ms 2308 KB Output is correct
7 Correct 4 ms 2308 KB Output is correct
8 Correct 3 ms 2308 KB Output is correct
9 Correct 2 ms 2308 KB Output is correct
10 Correct 8 ms 2712 KB Output is correct
11 Correct 2 ms 2712 KB Output is correct
12 Correct 13 ms 2896 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 5 ms 2308 KB Output is correct
7 Correct 4 ms 2308 KB Output is correct
8 Correct 3 ms 2308 KB Output is correct
9 Correct 2 ms 2308 KB Output is correct
10 Correct 8 ms 2712 KB Output is correct
11 Correct 2 ms 2712 KB Output is correct
12 Correct 13 ms 2896 KB Output is correct
13 Correct 2 ms 2896 KB Output is correct
14 Correct 2 ms 2896 KB Output is correct
15 Correct 939 ms 34420 KB Output is correct
16 Correct 15 ms 34420 KB Output is correct
17 Correct 129 ms 34420 KB Output is correct
18 Correct 227 ms 34420 KB Output is correct
19 Correct 1123 ms 38008 KB Output is correct
20 Correct 865 ms 38008 KB Output is correct
21 Correct 508 ms 38008 KB Output is correct
22 Correct 540 ms 38008 KB Output is correct
23 Correct 235 ms 38008 KB Output is correct
24 Correct 1573 ms 42784 KB Output is correct
25 Correct 1142 ms 42784 KB Output is correct
26 Correct 1293 ms 42784 KB Output is correct
27 Correct 1462 ms 42784 KB Output is correct