제출 #444749

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
444749		Dipra_Irham	Zapina (COCI20_zapina)	C++14	110 / 110	503 ms	3396 KiB

zapina

#include "bits/stdc++.h"
#define pb(x) push_back(x)
#define fil(x, y) memset(x, y, sizeof(x))
#define ll long long
#define ff first
#define ss second
#define printp(x) x.ff << " " << x.ss
#define pii pair<int,int>
#define pll pair<long long,long long>
#define mp(x, y) make_pair(x,y)
#define inf 1073741823
#define infll 4611686018427387903
#define M 1000000007
#define db(x) cout << x << " ";
#define N 357
#define sz size
#define sm 0.0000007
#define ins insert
#define ers erase
#define all(k) k.begin(), k.end()
#define cnt count
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;

ll mem[N][N][2];
ll ncr[N][N];

int n;
ll dp(int pos, int x, bool g)
{
    if(pos > n)
    {
        if(x == 0 && g == 1)
            return 1;
        return 0;
    }
    if(mem[pos][x][g] != -1)
        return mem[pos][x][g];
    ll ans = 0;
    for(int i = 0;i <= x;i++)
    {
        bool k = g;
        if(i == pos)
            k = 1;
        ans = (ans + (dp(pos + 1, x - i, k)*ncr[x][i]) % M) % M;
    }
    return mem[pos][x][g] = ans;
}
int main()
{
    fastio;
    cin >> n;
    fil(mem, -1);
    for(int i = 0;i <= 350;i++)
    {
        for(int j = 0;j <= i;j++)
        {
            if(j == 0 || j == i)
                ncr[i][j] = 1;
            else
            {
                ncr[i][j] = (ncr[i - 1][j - 1] + ncr[i - 1][j]) % M;
            }
        }
    }
    ll ans = dp(1, n, 0);
    cout << ans << endl;
    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55