Submission #528166

#	Time	Username	Problem	Language	Result	Execution time	Memory
528166		hoainiem	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	58 ms	16048 KiB

skyscraper

#include <bits/stdc++.h>
const int mod = 1e9+7;
double begintime, endtime;

using namespace std;
inline void CALC_TIME()
{    
    endtime = clock();
    cout<<"\nexecution time : "<<(endtime-begintime+1)/1000<<" s";
}
void add(int &x, int y)
{
    x += y;
    if(x >= mod)x -= mod;
}
int n, l, nect, ans = 0, tmp, a[108], f[108][108][1008][3];
int dq(int i, int j, int k, int x)
{
    if(k < 0 || k > l)return 0;
    if(f[i][j][k][x] != -1)return f[i][j][k][x];
    if(i == n)
    {
        if(j == 1 && k == l && x == 2)return f[i][j][k][x] = 1;
        return f[i][j][k][x] = 0;
    }
    int res = 0, tmp = a[i+2]-a[i+1];
    add(res, 1LL*dq(i+1, j+1, k+tmp*(j*2+2-x), x)*(j+1-x)%mod);
    if(x < 2)
        add(res, 1LL*dq(i+1, j+1, k+tmp*(j*2+1-x), x+1)*(2-x)%mod);
    add(res, 1LL*dq(i+1, j, k+tmp*(j*2-x), x)*(j*2-x)%mod);
    if(j != x)
    {
        if(j > 0)
            add(res, 1LL*dq(i+1, j-1, k+tmp*(j*2-2-x), x)*(j-1)%mod);
        if(x < 2)
            add(res, 1LL*dq(i+1, j+1, k+tmp*(j*2+1-x), x+1)*(2-x)%mod);
    }
    return f[i][j][k][x] = res;
}
int main()
{
    begintime = clock();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>l;
    for(int i = 1; i <= n; i++)
        cin>>a[i];
    if(n == 1)
    {
        cout<<1;
        return 0;
    }
    sort(a+1, a+n+1);
    a[0] = a[1];
    a[n+1] = a[n];
    f[0][0][0][0] = 1;
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= n; j++)
            for(int k = 0; k <= l; k++)
                for(int o = 0; o <= 2; o++)
                    if(f[i][j][k][o])
                    {
                        tmp = f[i][j][k][o];
                        nect = k+(j*2-o)*(a[i+1]-a[i]);
                        if(nect > l)continue;
                        add(f[i+1][j+1][nect][o], 1LL*tmp*(j+1-o)%mod);
                        if(o < 2)
                            add(f[i+1][j+1][nect][o+1], 1LL*tmp*(2-o)%mod);
                        if(j > 0)
                            add(f[i+1][j][nect][o], 1LL*tmp*(2*j-o)%mod);
                        if(j != o || i+1 == n)
                        {
                            if(j > 1)
                                add(f[i+1][j-1][nect][o], 1LL*tmp*(j-1)%mod);
                            if(o < 2 && j > 0)
                                add(f[i+1][j][nect][o+1], 1LL*tmp*(2-o)%mod);
                        }
                    }
    for(int i = 0; i <= l; i++)
        add(ans, f[n][1][i][2]);
    cout<<ans;
    return 0;
}

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