Submission #419887

#	Time	Username	Problem	Language	Result	Execution time	Memory
419887		cpp219	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	56 ms	23872 KiB

skyscraper

#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 1e3 + 9;
const ll mod = 1e9 + 7;
typedef pair<ll,ll> LL;

ll n,l,dp[101][101][1001][3],a[N];

void Add(ll &a,ll b){
    a = (a + b)%mod;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define task "tst"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    cin>>n>>l;
    for (ll i = 0;i < n;i++) cin>>a[i];
    sort(a,a + n); a[n] = 1000000;
    if (n == 1) return cout<<1,0;
    if (a[1] - a[0] <= l) dp[1][1][a[1] - a[0]][1] = 2;
    if (2*(a[1] - a[0]) <= l) dp[1][1][2*(a[1] - a[0])][0] = 1;
    //cout<<dp[1][1][2*(a[1] - a[0])][0]; return 0;
    for (ll i = 1;i < n;i++){
        ll diff = a[i + 1] - a[i];
        for (ll j = 1;j <= i;j++){
            for (ll k = 0;k <= l;k++){
                for (ll z = 0;z < 3;z++){
                    ll now = dp[i][j][k][z];
                    if (!now) continue;
                    //cout<<i<<" "<<j<<" "<<k<<" "<<z<<" ";
                    if (z < 2&&k + diff*(2*j - z - 1) <= l){
                        ll cur = k + diff*(2*j - z - 1);
                        if (i == n - 1) Add(dp[i + 1][j][cur][z + 1],now*(2 - z)*j);
                        else if (z == 0||j > 1) Add(dp[i + 1][j][cur][z + 1],now*(2 - z)*(j - z));
                        if (cur + 2*diff <= l) Add(dp[i + 1][j + 1][cur + 2*diff][z + 1],now*(2 - z));
                    }
                    if (k + diff*(2*j - z + 2) <= l)
                        Add(dp[i + 1][j + 1][k + diff*(2*j - z + 2)][z],now);
                    if (k + diff*(2*j - z) <= l)
                        Add(dp[i + 1][j][k + diff*(2*j - z)][z],now*(2*j - z));

                    if ((k + diff*(2*j - z - 2) <= l) && (j >= 2) && (i == n - 1 || j > 2 || z < 2)){
                        ll cur = k + diff*(2*j - z - 2);
                        if (!z) Add(dp[i + 1][j - 1][cur][z],now*j*(j - 1));
                        if (z == 1) Add(dp[i + 1][j - 1][cur][z],now*(j - 1)*(j - 1));
                        if (z == 2){
                            if (i == n - 1) Add(dp[i + 1][j - 1][cur][z],now);
                            else Add(dp[i + 1][j - 1][cur][z],now*(j - 2)*(j - 1));
                        }
                    }
                }
            }
        }
    }
    //return 0;
    ll ans = 0;
    for (ll i = 0;i <= l;i++) Add(ans,dp[n][1][i][2]);
    cout<<ans;
}

Compilation message (stderr)

skyscraper.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
skyscraper.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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