oj.uz

Submission #209868

# Submission time Handle Problem Language Result Execution time Memory
209868 2020-03-15T18:53:14 Z bash Tents (JOI18_tents) C++17
100 / 100
 236 ms 87460 KB 
/**
SXR0aXAkI0JwbXptI3FhI3Z3I293bCNqY2IjUG0jMCNicG0jVHFkcXZvLyNCcG0jQW10bjBhY2phcWFicXZvLyNNYm16dml0MSNWdyNhdGN1am16I2tpdiNhbXF9bSNQcXUjVnd6I0F0bW14MSNQcWEjaXptI2l0dCNicHF2b2EjUXYjYnBtI3BtaWRtdmEjaXZsI3d2I21pemJwMSNFcHcjcWEjYnBtem0ja2l2I3F2Ym16a21sbSNRdiNQcWEjeHptYW12a20jbXtrbXhiI0lhI3BtI3htenVxYmJtYnBHI1BtI3N2d2VtYnAjRXBpYiMraXh4bWl6bWJwI2J3I1BxYSNrem1pYmN6bWEjSWEsI0ptbnd6bSN3eiNJbmJteiN3eiNKbXBxdmwjYnBtdTEjVnd6I2FwaXR0I2JwbXwja3d1eGlhYSNJY29wYiN3biNwcWEjc3Z3ZXRtbG9tI017a214YiNpYSNQbSNlcXR0bWJwMSNQcWEjYnB6d3ZtI2x3YnAjbXtibXZsI1dkbXojYnBtI3BtaWRtdmEjSXZsI3d2I21pemJwLyNpdmwjUG0jbm1tdG1icCNWdyNuaWJxb2NtI3F2I29jaXpscXZvI0l2bCN4em1hbXpkcXZvI2JwbXUvI053eiNQbSNxYSNicG0jVXdhYiNQcW9wMSNCcG0jQWN4em11bSMrcXYjb3R3enwsMQ==
*/
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
 
#define F first
#define S second
#define endl '\n'
#define deb(x) cout<<#x<<' '<<x<<endl;
#define pb push_back
 using namespace __gnu_pbds;
using namespace std;

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
/*
#ifdef IZI_KATKA
#define int __int64_t
#else
#define int __int64
#endif
*/
const long long MOD = 1e9 + 7;
const long long MAXN = 1e6 + 1;

typedef long long ll;

#define pii pair<int,int>
 
long long readInt() {
    bool minus1 = false;
    long long result = 0;
    char ch;
    ch = getchar();
    while (true) {
        if (ch == '-') break;
        if (ch >= '0' && ch <= '9') break;
        ch = getchar();
    }
    if (ch == '-') minus1 = true; else result = ch-'0';
    while (true) {
        ch = getchar();
        if (ch < '0' || ch > '9') break;
        result = result*10 + (ch - '0');
    }
    if (minus1)
        return -result;
    else
        return result;
}

#define int ll

const int N = 3333;

int dp[N][N];
int solve(int n, int m) {
	if (~dp[n][m]) return dp[n][m];
	if (n == 0 || m == 0) {
		return dp[n][m] = 1;
	}
	int &ans = dp[n][m];
	ans = 0;
	ans += solve(n - 1, m);
	ans += 4 * m * solve(n - 1, m - 1);
	if (m >= 2)
		ans += (m * (m - 1) / 2) * solve(n - 1, m - 2);
	if (n >= 2)
		ans +=  m * (n - 1) * solve(n - 2, m - 1);
	ans %= MOD;	
	return ans;
}
main() {
	#ifdef IZI_KATKA
	assert(freopen("input", "r", stdin));
    assert(freopen("output", "w", stdout));
    #endif
    int n = readInt(), m = readInt();
    memset(dp, -1, sizeof(dp));
    cout << (solve(n, m) + MOD - 1) % MOD;
	return 0;
}

Compilation message

tents.cpp:100:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 87288 KB Output is correct
2 Correct 45 ms 87288 KB Output is correct
3 Correct 45 ms 87288 KB Output is correct
4 Correct 46 ms 87288 KB Output is correct
5 Correct 45 ms 87288 KB Output is correct
6 Correct 47 ms 87288 KB Output is correct
7 Correct 53 ms 87288 KB Output is correct
8 Correct 45 ms 87288 KB Output is correct
9 Correct 45 ms 87288 KB Output is correct
10 Correct 46 ms 87288 KB Output is correct
11 Correct 46 ms 87288 KB Output is correct
12 Correct 48 ms 87288 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 87288 KB Output is correct
2 Correct 45 ms 87288 KB Output is correct
3 Correct 45 ms 87288 KB Output is correct
4 Correct 46 ms 87288 KB Output is correct
5 Correct 45 ms 87288 KB Output is correct
6 Correct 47 ms 87288 KB Output is correct
7 Correct 53 ms 87288 KB Output is correct
8 Correct 45 ms 87288 KB Output is correct
9 Correct 45 ms 87288 KB Output is correct
10 Correct 46 ms 87288 KB Output is correct
11 Correct 46 ms 87288 KB Output is correct
12 Correct 48 ms 87288 KB Output is correct
13 Correct 45 ms 87288 KB Output is correct
14 Correct 45 ms 87416 KB Output is correct
15 Correct 174 ms 87416 KB Output is correct
16 Correct 47 ms 87288 KB Output is correct
17 Correct 56 ms 87288 KB Output is correct
18 Correct 72 ms 87288 KB Output is correct
19 Correct 207 ms 87416 KB Output is correct
20 Correct 159 ms 87420 KB Output is correct
21 Correct 111 ms 87288 KB Output is correct
22 Correct 121 ms 87416 KB Output is correct
23 Correct 83 ms 87460 KB Output is correct
24 Correct 236 ms 87416 KB Output is correct
25 Correct 211 ms 87416 KB Output is correct
26 Correct 206 ms 87416 KB Output is correct
27 Correct 232 ms 87416 KB Output is correct