oj.uz

Submission #649358

# Submission time Handle Problem Language Result Execution time Memory
649358 2022-10-10T05:26:14 Z ToroTN Skyscraper (JOI16_skyscraper) C++14
15 / 100
 2 ms 852 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,a[105],dp[105][105][1005][3],len,ans,cost;
void sum(ll a,ll b)
{
    a+=b;
    a%=1000000007;
}
ll md(ll a)
{return (a+1000000007)%1000000007;}
int main()
{
    scanf("%lld%lld",&n,&len);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    if(n==1)
    {
        printf("0\n");
        return 0;
    }
    sort(a+1,a+n+1);
    /*for(int i=1;i<=n;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");*/
    dp[1][1][0][0]=1;
    dp[1][1][0][1]=2;
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            for(int k=0;k<=len;k++)
            {
                for(int l=0;l<=2;l++)
                {
                    cost=md(md((2*(a[i+1]-a[i])*j)-(a[i+1]-a[i])*l));
                    if(k+cost>len)continue;
                    for(int c=-1;c<=1;c++)
                    {
                        if(j+c>=1)
                        {
                            if(c==0)
                            {
                                dp[i+1][j+c][k+cost][l]+=md(md(dp[i][j][k][l]*(j-1))*2);
                            }else
                            {
                                dp[i+1][j+c][k+cost][l]+=md(dp[i][j][k][l]*(j-1));
                            }
                            dp[i+1][j+c][k+cost][l]%=1000000007;
                            if(c>=0)
                            {
                                dp[i+1][j+c][k+cost][l]+=md(dp[i][j][k][l]*(2-l));
                                dp[i+1][j+c][k+cost][l]%=1000000007;
                            }
                        }
                    }
                    if(l<=1)
                    {
                        for(int c=0;c<=1;c++)
                        {
                            dp[i+1][j+c][k+cost][l+1]+=md(dp[i][j][k][l]*(2-l));
                            dp[i+1][j+c][k+cost][l+1]%=1000000007;
                        }
                    }
                }
            }
        }
    }
    //printf("%d\n",dp[2][2][2][0]);
    for(int i=0;i<=len;i++)
    {
        ans+=dp[n][1][i][2];
        ans%=1000000007;
    }
    printf("%lld\n",ans);
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 724 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -