oj.uz

Submission #44485

# Submission time Handle Problem Language Result Execution time Memory
44485 2018-04-02T12:30:59 Z imaxblue Tents (JOI18_tents) C++17
100 / 100
 449 ms 87548 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() ((rand() << 14)+rand())
#define scan(X) do{while((X=getchar())<'0'); for(X-='0'; '0'<=(_=getchar()); X=(X<<3)+(X<<1)+_-'0');}while(0)
char _;
#define pi 3.14159265358979323846

int add(int&A, int B){
    A=(A+B)%MN;
}
int mult(int&A, int B){
    A=(1LL*A*B)%MN;
}

int n, m, ncr[3005][3005]={1}, dp[3005][3005], seqpic[3005][3005];
int solve(int X, int Y){
    if (X==0) return 1;
    if (X<0 || Y<0) return 0;
    if (dp[X][Y]!=0) return dp[X][Y];
    add(dp[X][Y], solve(X-1, Y));
    add(dp[X][Y], 4LL*solve(X-1, Y-1)*Y%MN);
    //cout << step << ' ' << X << ' ' << Y << ' ' << dp[X][Y] << endl;
    return dp[X][Y];
}
int ans, x, y, x2, y2, t, t2;
int main(){
    fox(l, 3002){
        seqpic[l][0]=1;
        fox(l2, l+1){
            add(ncr[l+1][l2], ncr[l][l2]);
            add(ncr[l+1][l2+1], ncr[l][l2]);
        }
        fox(l2, l+1){
            if (l>1 && l2>0){
                seqpic[l][l2]=seqpic[l-2][l2-1];
                mult(seqpic[l][l2], ncr[l][2]);
                //cout << seqpic[l][l2] << ' ';
            }
        }
        //cout << endl;
    }
    cin >> n >> m;
    fox(l, n+2){
        x2=n-l;
        y2=m-l*2;
        if (x2<0 || y2<0) break;
        t=ncr[n][x2];
        mult(t, seqpic[m][l]);
        fox(l2, m+2){
            x=x2-l2*2;
            y=y2-l2;
            if (x<0 || y<0) break;
            t2=t;
            mult(t2, seqpic[x2][l2]);
            mult(t2, ncr[y2][y]);
            mult(t2, solve(x, y));
            //cout << x << ' ' << y << ' ' << t2/solve(x, y) << ' ' << solve(x, y)<< endl;
            add(ans, t2);
        }
    }
    cout << (ans+MN-1)%MN;
    return 0;
}

Compilation message

tents.cpp: In function 'int add(int&, int)':
tents.cpp:32:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
tents.cpp: In function 'int mult(int&, int)':
tents.cpp:35:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 55544 KB Output is correct
2 Correct 84 ms 55652 KB Output is correct
3 Correct 105 ms 55924 KB Output is correct
4 Correct 99 ms 56748 KB Output is correct
5 Correct 109 ms 56748 KB Output is correct
6 Correct 87 ms 56748 KB Output is correct
7 Correct 111 ms 56748 KB Output is correct
8 Correct 84 ms 56980 KB Output is correct
9 Correct 85 ms 56980 KB Output is correct
10 Correct 84 ms 57244 KB Output is correct
11 Correct 103 ms 57244 KB Output is correct
12 Correct 113 ms 57380 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 55544 KB Output is correct
2 Correct 84 ms 55652 KB Output is correct
3 Correct 105 ms 55924 KB Output is correct
4 Correct 99 ms 56748 KB Output is correct
5 Correct 109 ms 56748 KB Output is correct
6 Correct 87 ms 56748 KB Output is correct
7 Correct 111 ms 56748 KB Output is correct
8 Correct 84 ms 56980 KB Output is correct
9 Correct 85 ms 56980 KB Output is correct
10 Correct 84 ms 57244 KB Output is correct
11 Correct 103 ms 57244 KB Output is correct
12 Correct 113 ms 57380 KB Output is correct
13 Correct 93 ms 57380 KB Output is correct
14 Correct 98 ms 65276 KB Output is correct
15 Correct 379 ms 84728 KB Output is correct
16 Correct 93 ms 84728 KB Output is correct
17 Correct 104 ms 84728 KB Output is correct
18 Correct 142 ms 84728 KB Output is correct
19 Correct 449 ms 86360 KB Output is correct
20 Correct 326 ms 86360 KB Output is correct
21 Correct 190 ms 86360 KB Output is correct
22 Correct 218 ms 86360 KB Output is correct
23 Correct 156 ms 86360 KB Output is correct
24 Correct 432 ms 87548 KB Output is correct
25 Correct 331 ms 87548 KB Output is correct
26 Correct 376 ms 87548 KB Output is correct
27 Correct 426 ms 87548 KB Output is correct