Submission #439891

#	Time	Username	Problem	Language	Result	Execution time	Memory
439891		radal	Tents (JOI18_tents)	C++14	100 / 100	108 ms	71108 KiB

tents

#include <bits/stdc++.h>
#pragma GCC target ("avx,avx2,fma")
#pragma GCC optimization ("O8")
#pragma GCC optimization ("unroll-loops")
#define X first
#define Y second
#define debug(x) cerr << #x << ": " << x << endl;
#define endl '\n'
#define pb push_back
#define mp make_pair
#define rep(i,l,r) for (int i=l; i<r; i++)
#define repr(i,r,l) for (int i=r; i>=l; i--)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const long long int N=3e3+20,mod = 1e9+7,inf=2e18,dlt = 12250,maxm = 2e6;
int poww(ll a,int k){
    if (!k) return 1;
    if (k == 1) return a;
    ll r = poww(a,k/2);
    return (((r*r)%mod)*poww(a,k&1))%mod;
}
ll dp[N][N];
int main(){
    int h,w;
    cin >> h >> w;
    rep(i,0,w+1){
        dp[0][i] = 1;
        dp[1][i] = 4*i+1+i*(i-1)/2;
    }
    rep(i,1,h+1){
        dp[i][1] = 4*i+i*(i-1)/2+1;
        dp[i][0] = 1;
    }
    rep(i,2,h+1){
        rep(j,2,w+1){
            dp[i][j] = dp[i-1][j]+1ll*j*(j-1)*dp[i-1][j-2]/2;
            dp[i][j] %= mod;
            dp[i][j] += j*((dp[i-1][j-1]*4+(i-1)*dp[i-2][j-1])%mod);
            dp[i][j] %= mod;
        }
    }
    cout << (mod-1+dp[h][w])%mod;
}

Compilation message (stderr)

tents.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O8")
      | 
tents.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      |

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52