Submission #164293

#	Time	Username	Problem	Language	Result	Execution time	Memory
164293		kataki	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	627 ms	347512 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

ll dp[105][105][1005][2][2];
int n,l;
int a[105];
ll solve(int pos, int comp, int cost, int cl, int cr)
{
    if(comp < 0)
        return 0;
    int ncost = cost;
    if(pos > 0)
    {
        ncost += (cl+cr+2*comp) * abs(a[pos] - a[pos-1]);
    } 
    if(ncost > l)
        return 0;
    if(pos == n-1)
    {
        return comp == 0;
    }
    ll &ans = dp[pos][comp][cost][cl][cr];
    if(ans != -1)
        return ans;
    ans = 0;
    
    ans += solve(pos+1, comp, ncost, 1, cr);
    ans += solve(pos+1, comp-1, ncost, 1, cr) * comp;

    ans += solve(pos+1, comp, ncost, cl, 1);
    ans += solve(pos+1, comp-1, ncost, cl, 1) * comp;


    ans += solve(pos+1, comp, ncost, cl, cr) * (2 * comp);
    ans += solve(pos+1, comp-1, ncost, cl, cr) * (comp) * (comp-1);
    
    ans += solve(pos+1, comp+1, ncost, cl, cr);
    
    ans %= mod;
    return ans;
       
}

int main()
{
    memset(dp,-1,sizeof(dp));
    scanf("%d %d",&n,&l);
    for(int i = 0; i < n; i++)
        scanf("%d",&a[i]);
    sort(a, a+n);
    printf("%lld\n",solve(0,0,0,0,0));
    return 0;
}

Compilation message (stderr)

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

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