Submission #1193920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193920		Muhammad_Aneeq	Skyscraper (JOI16_skyscraper)	C++20	20 / 100	57 ms	50248 KiB

skyscraper

#include <iostream>
#include <algorithm>
using namespace std;
int const N=110,L=1005,mod=1e9+7;
int dp[N][N][4][L]={};
inline void solve()
{
    int n,lo;
    cin>>n>>lo;
    int a[n+1];
    for (int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    dp[1][1][0][0]=1;
    dp[1][1][1][0]=2;
    if (n==1)
        dp[1][1][2][0]=1;
    for (int i=1;i<n;i++)
    {
        for (int j=1;j<=i;j++)
        {
            for (int k=0;k<3;k++)
            {
                int cost=(a[i+1]-a[i])*(2*j-k);
                for (int l=cost;l<=lo;l++)
                {
                    dp[i+1][j+1][k][l]+=(dp[i][j][k][l-cost]*(j+1-k));
                    dp[i+1][j][k][l]+=(dp[i][j][k][l-cost]*(2*j-k));
                    dp[i+1][j-1][k][l]+=(dp[i][j][k][l-cost]*(j-1));
                    dp[i+1][j+1][k+1][l]+=(dp[i][j][k][l-cost]*(2-k));
                    dp[i+1][j][k+1][l]+=(dp[i][j][k][l-cost]*(2-k));
                    dp[i+1][j+1][k][l]%=mod;
                    dp[i+1][j][k][l]%=mod;
                    dp[i+1][j-1][k][l]%=mod;
                    dp[i+1][j+1][k+1][l]%=mod;
                    dp[i+1][j][k+1][l]%=mod;
                }
            }
        }
    }
    int ans=0;
    for (int i=0;i<=L;i++)
    {
        ans+=(dp[n][1][2][i]);
        ans%=mod;
    }
    cout<<ans<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}

Compilation message (stderr)

skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:44:28: warning: iteration 1005 invokes undefined behavior [-Waggressive-loop-optimizations]
   44 |         ans+=(dp[n][1][2][i]);
      |              ~~~~~~~~~~~~~~^~
skyscraper.cpp:42:19: note: within this loop
   42 |     for (int i=0;i<=L;i++)
      |                  ~^~~

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