oj.uz

Submission #869314

# Submission time Handle Problem Language Result Execution time Memory
869314 2023-11-04T03:01:17 Z 12345678 Tents (JOI18_tents) C++17
0 / 100
 2 ms 13776 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int mod=1e9+7, nx=3e3+5;
ll h, w, dp[nx][nx], qs[nx][nx], ans[nx][nx];

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>h>>w;
    for (int i=1; i<=h; i++)
    {
        for (int j=1; j<=w; j++)
        {
            dp[i][j]=((ans[i-1][j-1]+1)*4)%mod;
            dp[i][j]=(dp[i][j]+qs[i-1][j-1]*4*(j-1))%mod;
            //cout<<"here1"<<' '<<i<<' '<<j<<' '<<dp[i][j]<<'\n';
            if (j>=2)
            {
                dp[i][j]=(dp[i][j]+(j-1)*(ans[i-1][j-2]+1))%mod;
                dp[i][j]=(dp[i][j]+(j-1)*(j-2)/2*qs[i-1][j-2])%mod;
            }
            //cout<<"here2"<<' '<<i<<' '<<j<<' '<<dp[i][j]<<'\n';
            if (i>=2) 
            {
                dp[i][j]=(dp[i][j]+(i-1)*(ans[i-2][j-1]+1))%mod;
                dp[i][j]=(dp[i][j]+(j-1)*(i-1)*qs[i-2][j-1])%mod;
            }
            //cout<<"here3"<<' '<<i<<' '<<j<<' '<<dp[i][j]<<'\n';
            ans[i][j]=(ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1]+dp[i][j])%mod;
            qs[i][j]=(qs[i-1][j]+dp[i][j])%mod;
            //cout<<i<<' '<<j<<' '<<dp[i][j]<<' '<<ans[i][j]<<'\n';
        }
    }
    cout<<ans[h][w];
}

Subtask #1
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 2 ms 13776 KB Output is correct
5 Incorrect 1 ms 7260 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 2 ms 13776 KB Output is correct
5 Incorrect 1 ms 7260 KB Output isn't correct
6 Halted 0 ms 0 KB -