oj.uz

Submission #50485

# Submission time Handle Problem Language Result Execution time Memory
50485 2018-06-11T06:49:52 Z top34051 Tents (JOI18_tents) C++17
0 / 100
 2000 ms 77664 KB 
    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int maxn = 3005;
    const ll mod = 1e9+7;
    int n,m;
    unordered_map<int,unordered_map<int,unordered_map<int,ll>>> dp;
    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:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&n,&m);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
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 428 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 88 ms 4404 KB Output is correct
6 Correct 839 ms 33604 KB Output is correct
7 Correct 266 ms 33604 KB Output is correct
8 Correct 380 ms 33604 KB Output is correct
9 Correct 4 ms 33604 KB Output is correct
10 Execution timed out 2047 ms 77664 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #2
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 428 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 88 ms 4404 KB Output is correct
6 Correct 839 ms 33604 KB Output is correct
7 Correct 266 ms 33604 KB Output is correct
8 Correct 380 ms 33604 KB Output is correct
9 Correct 4 ms 33604 KB Output is correct
10 Execution timed out 2047 ms 77664 KB Time limit exceeded
11 Halted 0 ms 0 KB -