oj.uz

답안 #50467

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
50467 2018-06-11T05:22:39 Z top34051 Tents (JOI18_tents) C++17
48 / 100
 1140 ms 109400 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 305;
const ll mod = 1e9+7;
int n,m;
ll dp[maxn][maxn][maxn];
ll add(ll x, ll y) {
    return ((x+y)%mod + mod)%mod;
}
ll mul(ll x, ll y) {
    return ((x*y)%mod + mod)%mod;
}
ll comb(ll x) {
    return ((x*(x-1)/2)%mod + mod)%mod;
}
ll f(int x, int need, int free) {
    if(x==n+1) return 1;
    if(!dp[x][need][free]) {
        ll res = 0;
        //nothing
        res = add(res, f(x+1,need,free));
        //point to south
        if(free>=1) res = add(res, mul(free, f(x+1,need+1,free-1)));
        //point to north
        if(free>=1) res = add(res, mul(free, f(x+1,need,free-1)));
        if(need>=1) res = add(res, mul(need, f(x+1,need-1,free)));
        //point to west and east
        if(free>=1) res = add(res, mul(free, f(x+1,need,free-1)));
        if(free>=1) res = add(res, mul(free, f(x+1,need,free-1)));
        if(free>=2) res = add(res, mul(comb(free), f(x+1,need,free-2)));
        dp[x][need][free] = res;
    }
    return dp[x][need][free];
}
int main() {
    scanf("%d%d",&n,&m);
    printf("%lld",add(f(1,0,m),-1));
}

Compilation message

tents.cpp: In function 'int main()':
tents.cpp:37: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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 904 KB Output is correct
4 Correct 4 ms 2736 KB Output is correct
5 Correct 16 ms 5476 KB Output is correct
6 Correct 117 ms 39892 KB Output is correct
7 Correct 38 ms 39892 KB Output is correct
8 Correct 73 ms 39892 KB Output is correct
9 Correct 4 ms 39892 KB Output is correct
10 Correct 347 ms 74568 KB Output is correct
11 Correct 2 ms 74568 KB Output is correct
12 Correct 1140 ms 109400 KB Output is correct

Subtask #2
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 904 KB Output is correct
4 Correct 4 ms 2736 KB Output is correct
5 Correct 16 ms 5476 KB Output is correct
6 Correct 117 ms 39892 KB Output is correct
7 Correct 38 ms 39892 KB Output is correct
8 Correct 73 ms 39892 KB Output is correct
9 Correct 4 ms 39892 KB Output is correct
10 Correct 347 ms 74568 KB Output is correct
11 Correct 2 ms 74568 KB Output is correct
12 Correct 1140 ms 109400 KB Output is correct
13 Correct 2 ms 109400 KB Output is correct
14 Runtime error 8 ms 109400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -