Submission #442761

#	Time	Username	Problem	Language	Result	Execution time	Memory
442761		Bench0310	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	594 ms	5364 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    const ll mod=1000000007;
    auto add=[&](ll a,ll b)->ll{return (a+b)%mod;};
    auto madd=[&](ll &a,ll b){a=add(a,b);};
    auto mul=[&](ll a,ll b)->ll{return (a*b)%mod;};
    int n,l;
    cin >> n >> l;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    sort(a.begin(),a.end());
    a.push_back(0);
    vector dp(n+1,vector(l+1,array<ll,3>{0,0,0}));
    dp[0][0][0]=1;
    auto c=[&](int i,int e,int x)->int{return (2*i-e)*x;};
    for(int o=0;o<n;o++)
    {
        vector ndp(n+1,vector(l+1,array<ll,3>{0,0,0}));
        auto upd=[&](int i,int j,int e,ll val)
        {
            j+=c(i,e,a[o+1]);
            if(1<=i&&i<=n&&0<=j&&j<=l&&0<=e&&e<=2) madd(ndp[i][j][e],val);
        };
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=l;j++)
            {
                for(int e=0;e<=2;e++)
                {
                    int nj=j-c(i,e,a[o]);
                    //create a new group
                    upd(i+1,nj-2*a[o],e,mul(i+1-e,dp[i][j][e]));
                    //create a new group as an end
                    upd(i+1,nj-a[o],e+1,mul(2-e,dp[i][j][e]));
                    //add to a group
                    upd(i,nj,e,mul(2*i-e,dp[i][j][e]));
                    //add to a group as an end
                    upd(i,nj+a[o],e+1,mul(2-e,dp[i][j][e]));
                    //merge two groups
                    if(i>=2) upd(i-1,nj+2*a[o],e,mul(i-1,dp[i][j][e]));
                }
            }
        }
        dp=ndp;
    }
    ll res=(n==1);
    for(int j=0;j<=l;j++) madd(res,dp[1][j][2]);
    cout << res << "\n";
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80