SRM 694 Div2 Hard.

UpDownNess.cpp

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
#define ITR(i,c) for(auto i=begin(c);i!=end(c);i++)
#define FORE(x,arr) for(auto &x:arr)
#define FOR(i,a,n) for(int i=a;i<(int)(n);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(c) begin(c),end(c)
const int DX[4]={0,1,0,-1}, DY[4]={-1,0,1,0};
const int INF = 1e9;
template<class T,class U>ostream&operator<<(ostream &os,const pair<T,U> &p){
    os<<"("<<p.first<<","<<p.second<<")";return os;}
template<class T>ostream&operator<<(ostream &os,const vector<T> &v){
    ITR(i,v)os<<*i<<(i==end(v)-1?"":" ");return os;}
//-----------------------------------------------------------

static const int MOD = 1000000007;
struct UpDownNess {
    ll dp[52][5001];
    int count(int N, int K) {
        dp[1][0]=1;
        FOR(i,1,N+1) {
            REP(j,i+1) {
                REP(k,K+1) {
                    if(k+(j*(i-j))<=K)
                        dp[i+1][k+(j*(i-j))] += (dp[i][k] % MOD);
                }
            }
        }
        return (dp[N][K] % MOD);
    }
};