Submission #78166

#	Time	Username	Problem	Language	Result	Execution time	Memory
78166		aquablitz11	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	168 ms	22440 KiB

skyscraper

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

using ll = long long;
const int N = 110;
const int L = 1010;
const int MOD = 1e9+7;

int n, l;
int A[N], dp[N][N][L][3];
bool vis[N][N][L][3];

ll solve(int i, int comp, int val, int ends)
{
    if (comp == 0 || val > l || ends == 3) return 0;
    if (i == n+1)
        return comp==1 && val<=l && ends==2 ? 1 : 0;

    if (vis[i][comp][val][ends]) return dp[i][comp][val][ends];
    vis[i][comp][val][ends] = true;

    int x = val+(2*comp-ends)*(A[i]-A[i-1]);

    ll ans = 0;
    // add new component
    ans = (ans + (comp+1-ends)*solve(i+1, comp+1, x, ends)) % MOD;
    // add new component to an end
    ans = (ans + (2-ends)*solve(i+1, comp+1, x, ends+1)) % MOD;
    // append to any components normally
    ans = (ans + (2*comp-ends)*solve(i+1, comp, x, ends)) % MOD;
    // append to a component and mark as an end
    ans = (ans + (2-ends)*solve(i+1, comp, x, ends+1)) % MOD;
    // merge components
    ans = (ans + (comp-1)*solve(i+1, comp-1, x, ends)) % MOD;

    //printf("dp[%d][%d][%d][%d] = %lld\n", i, comp, val, ends, ans);
    return dp[i][comp][val][ends] = ans;
}

int main()
{
    scanf("%d%d", &n, &l);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &A[i]);
    sort(A+1, A+n+1);
    ll ans = n == 1 ? 1 : (solve(2,1,0,0)+2*solve(2,1,0,1))%MOD;
    printf("%lld\n", ans);

    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:42: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:44: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