Submission #681605

#	Time	Username	Problem	Language	Result	Execution time	Memory
681605		vjudge1	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	193 ms	83768 KiB

skyscraper

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100 +2;
const int M = 1000 +2;
const int mod = 1e9+7;
typedef pair<int,int> pii;

inline int add(int x, int y)
{
    return (x+y>=mod ? x+y-mod : x+y);
}

inline int gun(int x, int y)
{
    return ((x*1ll*y)%mod);
}

int n,l;
int a[N];
int dp[N][N][M][3];

int32_t main()
{
    scanf("%d %d",&n,&l);
    for(int i=0; i<n; i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a,a+n);
    if(n==1)
    {
        cout<<"1\n";
        return 0;
    }
    for(int sum =0 ; sum<=l; sum++)
        dp[n][1][sum][2] = 1;

    for(int idx=n-1; idx>=0; idx--)
    {
        int prv = (idx-1>=0?a[idx-1] : 0);
        for(int comps = min(1,idx); comps <= n; comps++)
        {
            for(int sum =0 ; sum<=l; sum++)
            {
                for(int matha = 0 ; matha <= 2; matha++)
                {
                    int notun = sum + (a[idx]-prv)*(2*comps - matha);
                    if(notun > l)
                        continue;
                    int ans = 0;
                    //Create
                    ans = add(ans, gun(comps+1 - matha, dp[idx+1][comps+1][notun][matha]));
                    //merge
                    if(comps >= 2)
                        ans = add(ans, gun(comps-1, dp[idx+1][comps-1][notun][matha])) ;
                    //add
                    if(comps>=1)
                        ans = add(ans, gun(2*comps-matha, dp[idx+1][comps][notun][matha]));

                    if(matha < 2){
                        ans = add(ans, gun(2-matha, dp[idx+1][comps+1][notun][matha+1]));
                        ans = add(ans, gun(2-matha, dp[idx+1][comps][notun][matha+1]));
                    }
                    dp[idx][comps][sum][matha] = ans;
                }
            }
        }
    }
    printf("%d\n",dp[0][0][0][0]);
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int32_t main()':
skyscraper.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d %d",&n,&l);
      |     ~~~~~^~~~~~~~~~~~~~~
skyscraper.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~

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