답안 #1112034

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1112034	2024-11-13T14:35:20 Z	Icelast	Tents (JOI18_tents)	C++17	100 / 100	141 ms	70992 KB

tents

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9, mod = 1e9+7, inv2 = (mod+1)/2;
void solve(){
    int n, m;
    cin >> n >> m;
    vector<vector<ll>> f(n+1, vector<ll>(m+1, 0)); // consider problem FILL (not rectangle) from (1, 1) to (i, j)
    for(int i = 1; i <= n; i++) f[i][0] = 1;
    for(int j = 0; j <= m; j++) f[0][j] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            //nothing on ith row
            f[i][j] += f[i-1][j];
            //place one thing on ith row
            f[i][j] += f[i-1][j-1] * (j*4)%mod;
            //place 2 horizontally
            if(j-2 >= 0) f[i][j] += f[i-1][j-2] * (j*(j-1)%mod*inv2%mod)%mod;
            //place 2 vertically
            if(i-2 >= 0) f[i][j] += f[i-2][j-1] * (j*(i-1)%mod)%mod;
            f[i][j] %= mod;
        }
    }
    cout << f[n][m]-1;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Subtask #1

48.0 / 48.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	500 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	588 KB	Output is correct
6	Correct	1 ms	764 KB	Output is correct
7	Correct	1 ms	592 KB	Output is correct
8	Correct	1 ms	500 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	2 ms	592 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	3 ms	1104 KB	Output is correct

Subtask #2

52.0 / 52.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	500 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	588 KB	Output is correct
6	Correct	1 ms	764 KB	Output is correct
7	Correct	1 ms	592 KB	Output is correct
8	Correct	1 ms	500 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	2 ms	592 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	3 ms	1104 KB	Output is correct
13	Correct	1 ms	504 KB	Output is correct
14	Correct	1 ms	336 KB	Output is correct
15	Correct	89 ms	44132 KB	Output is correct
16	Correct	6 ms	3152 KB	Output is correct
17	Correct	22 ms	10064 KB	Output is correct
18	Correct	25 ms	12624 KB	Output is correct
19	Correct	100 ms	51536 KB	Output is correct
20	Correct	81 ms	41140 KB	Output is correct
21	Correct	52 ms	27216 KB	Output is correct
22	Correct	51 ms	26960 KB	Output is correct
23	Correct	30 ms	15184 KB	Output is correct
24	Correct	141 ms	70992 KB	Output is correct
25	Correct	99 ms	52816 KB	Output is correct
26	Correct	115 ms	60536 KB	Output is correct
27	Correct	141 ms	68168 KB	Output is correct