oj.uz

Submission #551416

# Submission time Handle Problem Language Result Execution time Memory
551416 2022-04-20T15:28:17 Z Soul234 Tents (JOI18_tents) C++14
100 / 100
 239 ms 71312 KB 
#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}

const int MOD = 1e9 + 7;
const int MX = 3005;

ll dp[MX][MX];
int H, W;

int add(int a, int b) {
    if((a += b) >= MOD) a-=MOD;
    return a;
}

ll mul(ll a, ll b) {
    return 1LL*a*b%MOD;
}

ll calc(int h, int w) {
    if(h <= 0 || w <= 0) return 1;
    if(~dp[h][w]) return dp[h][w];
    ll &res = dp[h][w];
    res = 0;
    res = add(res, calc(h-1, w));
    res = add(res, mul(4, mul(w, calc(h-1, w-1))));
    res = add(res, mul(1LL*w*(w-1)/2, calc(h-1, w-2)));
    res = add(res, mul(1LL*w*(h-1), calc(h-2, w-1)));
    return res;
}

void solve() {
    memset(dp, -1, sizeof dp);
    cin>>H>>W;
    cout << add(calc(H, W), MOD-1) << nl;
}

int main() {
    setIO();

    int t=1;
    //cin>>t;
    while(t-->0) {
        solve();
    }

    return 0;
}

Compilation message

tents.cpp: In function 'void setIO(std::string)':
tents.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tents.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 70996 KB Output is correct
2 Correct 29 ms 70988 KB Output is correct
3 Correct 27 ms 70980 KB Output is correct
4 Correct 27 ms 70956 KB Output is correct
5 Correct 28 ms 70912 KB Output is correct
6 Correct 29 ms 70996 KB Output is correct
7 Correct 29 ms 70964 KB Output is correct
8 Correct 30 ms 70904 KB Output is correct
9 Correct 27 ms 70952 KB Output is correct
10 Correct 28 ms 71012 KB Output is correct
11 Correct 28 ms 71008 KB Output is correct
12 Correct 29 ms 71000 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 70996 KB Output is correct
2 Correct 29 ms 70988 KB Output is correct
3 Correct 27 ms 70980 KB Output is correct
4 Correct 27 ms 70956 KB Output is correct
5 Correct 28 ms 70912 KB Output is correct
6 Correct 29 ms 70996 KB Output is correct
7 Correct 29 ms 70964 KB Output is correct
8 Correct 30 ms 70904 KB Output is correct
9 Correct 27 ms 70952 KB Output is correct
10 Correct 28 ms 71012 KB Output is correct
11 Correct 28 ms 71008 KB Output is correct
12 Correct 29 ms 71000 KB Output is correct
13 Correct 26 ms 70876 KB Output is correct
14 Correct 27 ms 71124 KB Output is correct
15 Correct 160 ms 71280 KB Output is correct
16 Correct 29 ms 70932 KB Output is correct
17 Correct 39 ms 70984 KB Output is correct
18 Correct 54 ms 71048 KB Output is correct
19 Correct 182 ms 71300 KB Output is correct
20 Correct 142 ms 71196 KB Output is correct
21 Correct 92 ms 71168 KB Output is correct
22 Correct 101 ms 71220 KB Output is correct
23 Correct 67 ms 71308 KB Output is correct
24 Correct 239 ms 71312 KB Output is correct
25 Correct 176 ms 71268 KB Output is correct
26 Correct 201 ms 71292 KB Output is correct
27 Correct 228 ms 71304 KB Output is correct