oj.uz

Submission #809917

# Submission time Handle Problem Language Result Execution time Memory
809917 2023-08-06T04:10:13 Z winter0101 Tents (JOI18_tents) C++14
48 / 100
 238 ms 283496 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define eb emplace_back
const long long du=1e9+7;
long long f[301][301][301];
long long combi[3001][3001];
long long pw[3001];
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    int m,n;
    cin>>m>>n;
    pw[0]=1;
    for1(i,1,3000)pw[i]=(pw[i-1]*4)%du;
    combi[0][0]=1;
    for1(i,1,3000){
    combi[i][0]=1;
    for1(j,1,3000){
    combi[i][j]=(combi[i-1][j-1]+combi[i-1][j])%du;
    }
    }
    f[0][0][0]=1;
    for1(i,1,m){
    for1(j,0,n){
    for1(k,0,n){
    if (j+k>n)break;
    //j take 1 k take 2
    int can=n-j-k;
    f[i][j][k]=(f[i][j][k]+f[i-1][j][k])%du;
    if (j+1+k<=n){
        f[i][j+1][k]=(f[i][j+1][k]+f[i-1][j][k]*can)%du;
    }
    if (j-1>=0){
        f[i][j-1][k+1]=(f[i][j-1][k+1]+f[i-1][j][k]*j)%du;
    }
    if (j+k+2<=n){
        f[i][j][k+2]=(f[i][j][k+2]+f[i-1][j][k]*combi[can][2])%du;
    }
    }
    }
    }
    long long ans=0;
    for1(j,0,n){
    for1(k,0,n){
    ans=(ans+f[m][j][k]*pw[j])%du;
    }
    }
    cout<<(ans-1+du)%du;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 70776 KB Output is correct
2 Correct 46 ms 71684 KB Output is correct
3 Correct 41 ms 71140 KB Output is correct
4 Correct 48 ms 72900 KB Output is correct
5 Correct 76 ms 108488 KB Output is correct
6 Correct 80 ms 118616 KB Output is correct
7 Correct 80 ms 117668 KB Output is correct
8 Correct 67 ms 106180 KB Output is correct
9 Correct 49 ms 72536 KB Output is correct
10 Correct 110 ms 166472 KB Output is correct
11 Correct 49 ms 77808 KB Output is correct
12 Correct 238 ms 283496 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 70776 KB Output is correct
2 Correct 46 ms 71684 KB Output is correct
3 Correct 41 ms 71140 KB Output is correct
4 Correct 48 ms 72900 KB Output is correct
5 Correct 76 ms 108488 KB Output is correct
6 Correct 80 ms 118616 KB Output is correct
7 Correct 80 ms 117668 KB Output is correct
8 Correct 67 ms 106180 KB Output is correct
9 Correct 49 ms 72536 KB Output is correct
10 Correct 110 ms 166472 KB Output is correct
11 Correct 49 ms 77808 KB Output is correct
12 Correct 238 ms 283496 KB Output is correct
13 Incorrect 79 ms 75060 KB Output isn't correct
14 Halted 0 ms 0 KB -