Submission #159106

#	Time	Username	Problem	Language	Result	Execution time	Memory
159106		ppnxblstr	Tents (JOI18_tents)	C++14	100 / 100	121 ms	35668 KiB

tents

#include <bits/stdc++.h>
using namespace std;
int dp[3005][3005];
const int MOD = 1e9+7;
int main(){
    int h,w;
    scanf("%d%d",&h,&w);
    for(int i = 1; i < 3005; i++){
        dp[1][i] = 1ll * i * (i-1) / 2ll + 4ll * i + 1ll;
        dp[1][i] %= 1ll * MOD;
        dp[i][1] = dp[1][i];
        dp[0][i] = dp[i][0] = 1ll;
    }
    dp[0][0] = 1ll;
    for(int r = 2; r <= h; r++){
        for(int c = 2; c <= w; c++){
            long long l = 1ll * r * (r-1ll) / 2ll;
            l %= 1ll * MOD;
            l *= 1ll * dp[r-2][c-1];
            l %= 1ll * MOD;
            l += 1ll * (c-1) * r * dp[r-1][c-2];
            l %= 1ll * MOD;
            l += 4ll * r * dp[r-1][c-1];
            l %= 1ll * MOD;
            l += 1ll * dp[r][c-1];
            l %= 1ll * MOD;
            dp[r][c] = l;
        }
    }
    printf("%d\n",(dp[h][w]+MOD-1) % MOD);
    return 0;
}

Compilation message (stderr)

tents.cpp: In function 'int main()':
tents.cpp:7:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&h,&w);
     ~~~~~^~~~~~~~~~~~~~

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