oj.uz

Submission #50492

# Submission time Handle Problem Language Result Execution time Memory
50492 2018-06-11T07:14:24 Z top34051 Tents (JOI18_tents) C++17
100 / 100
 929 ms 59460 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 3005;
const ll mod = 1e9+7;
int n,m;
ll dp[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 free) {
    if(x==n+1) return 1;
    if(!dp[x][free]) {
        ll res = 0;
        //nothing
        res = add(res, f(x+1,free));
        //point to south
        if(free>=1) res = add(res, mul(free, f(x+1,free-1)));
        //also select point to north
        if(x!=n && free>=1) res = add(res, mul(mul(free, n-x), f(x+2,free-1)));
        //point to north
        if(free>=1) res = add(res, mul(free, f(x+1,free-1)));
        //point to west and east
        if(free>=1) res = add(res, mul(free, f(x+1,free-1)));
        if(free>=1) res = add(res, mul(free, f(x+1,free-1)));
        if(free>=2) res = add(res, mul(comb(free), f(x+1,free-2)));
        dp[x][free] = res;
//        printf("dp %d %d = %d\n",x,free,dp[x][free]);
    }
    return dp[x][free];
}
int main() {
    scanf("%d%d",&n,&m);
    printf("%lld",add(f(1,m),-1));
}

Compilation message

tents.cpp: In function 'int main()':
tents.cpp:39: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 3 ms 376 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 4 ms 1260 KB Output is correct
5 Correct 3 ms 1260 KB Output is correct
6 Correct 5 ms 1560 KB Output is correct
7 Correct 3 ms 1560 KB Output is correct
8 Correct 6 ms 1708 KB Output is correct
9 Correct 2 ms 1708 KB Output is correct
10 Correct 9 ms 2092 KB Output is correct
11 Correct 2 ms 2092 KB Output is correct
12 Correct 11 ms 2272 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 3 ms 376 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 4 ms 1260 KB Output is correct
5 Correct 3 ms 1260 KB Output is correct
6 Correct 5 ms 1560 KB Output is correct
7 Correct 3 ms 1560 KB Output is correct
8 Correct 6 ms 1708 KB Output is correct
9 Correct 2 ms 1708 KB Output is correct
10 Correct 9 ms 2092 KB Output is correct
11 Correct 2 ms 2092 KB Output is correct
12 Correct 11 ms 2272 KB Output is correct
13 Correct 2 ms 2272 KB Output is correct
14 Correct 14 ms 10084 KB Output is correct
15 Correct 608 ms 47636 KB Output is correct
16 Correct 9 ms 47636 KB Output is correct
17 Correct 59 ms 47636 KB Output is correct
18 Correct 126 ms 47636 KB Output is correct
19 Correct 734 ms 53924 KB Output is correct
20 Correct 502 ms 53924 KB Output is correct
21 Correct 322 ms 53924 KB Output is correct
22 Correct 358 ms 53924 KB Output is correct
23 Correct 199 ms 53924 KB Output is correct
24 Correct 929 ms 59460 KB Output is correct
25 Correct 617 ms 59460 KB Output is correct
26 Correct 706 ms 59460 KB Output is correct
27 Correct 806 ms 59460 KB Output is correct