제출 #1191258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191258		alexdd	JOIRIS (JOI16_joiris)	C++20	0 / 100	2 ms	2880 KiB

joiris

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;

const int MAXN = 105;

int n,lim;
int a[105];
int dp[105][105][1005][5];
signed main()
{
    cin>>n>>lim;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    if(n==1)
    {
        cout<<1;
        return 0;
    }
    sort(a+1,a+1+n);
    dp[0][0][0][0] = 1;
    int rez=0;
    for(int i=1;i<=n;i++)
    {
        for(int cnt=0;cnt<=i-1;cnt++)
        {
            for(int sum=0;sum<=lim;sum++)
            {
                for(int margini=0;margini<=2;margini++)
                {
                    dp[i-1][cnt][sum][margini] %= MOD;
                    int x = dp[i-1][cnt][sum][margini];

                    if(x==0)
                        continue;

                    int newsum = sum + (a[i]-a[i-1])*(2*cnt - margini);

                    if(newsum > lim)
                        continue;

                    dp[i][cnt + 1][newsum][margini] += x;///incepe o secv noua
                    dp[i][cnt + 1][newsum][margini + 1] += x*(2-margini);///incepe o secv noua la margine
                    dp[i][cnt][newsum][margini] += x * (2*cnt - margini);///se continua o secv
                    if(cnt-1 >= 1) dp[i][cnt - 1][newsum][margini] += x * ((cnt-margini)*(cnt-margini-1) + margini * (cnt-margini));///se unesc 2 secv
                    dp[i][cnt][newsum][margini + 1] += x * (2-margini) * (cnt - margini);

                    if(i==n)
                    {
                        if(cnt==1 && margini==1)
                        {
                            rez += x;
                        }
                        if(cnt==2 && margini==2)
                        {
                            rez += x;
                        }
                    }
                }
            }
        }
    }
    cout<<rez%MOD;
    return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 55