Submission #520230

#	Time	Username	Problem	Language	Result	Execution time	Memory
520230		kevin	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	375 ms	131980 KiB

skyscraper

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

#define ll long long
#define nl cout<<"\n"
#define ca(v) for(auto i:v) cout<<i<<" ";

const int MOD = 1e9 + 7;

ll dp[102][102][1002][3];

int main()
{
    // ios_base::sync_with_stdio(0); cin.tie(0);
    if (fopen("input.in", "r")) freopen("input.in", "r", stdin);
    int n, l;
    cin>>n>>l;
    int ar[n];
    for(int i=0; i<n; i++) cin>>ar[i];
    if(n == 1) { cout<< 1; return 0; }
    sort(ar, ar+n);
    dp[0][0][0][0] = 1;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            for(int v=0; v<=l; v++){
                for(int r=0; r<3; r++){
                    int d = ar[i] - (i?ar[i-1]:0);
                    int nx = v + d * (j * 2 - r);
                    if(nx > l || nx < 0) continue;
                    // merge 2
                    if(j) dp[i+1][j-1][nx][r] = (dp[i+1][j-1][nx][r] + dp[i][j][v][r] * (j-1) % MOD) % MOD;
                    // add to exsisting
                    dp[i+1][j][nx][r] = (dp[i+1][j][nx][r] + dp[i][j][v][r] * (2*j-r) % MOD) % MOD;
                    // cout<<i+1<<"|"<<j<<"|"<<nx<<"|"<<r<<"|"<<dp[i+1][j][nx][r];
                    // add to exsisting and -1
                    if(r<2) dp[i+1][j][nx][r+1] = (dp[i+1][j][nx][r+1] + dp[i][j][v][r] * (2-r) % MOD) % MOD;
                    // make new
                    dp[i+1][j+1][nx][r] = (dp[i+1][j+1][nx][r] + dp[i][j][v][r] * (j+1-r) % MOD) % MOD;
                    // make new and -1
                    if(r<2) dp[i+1][j+1][nx][r+1] = (dp[i+1][j+1][nx][r+1] + dp[i][j][v][r] * (2-r) % MOD) % MOD;
                }
            }
        }
    }
    int tot = 0;
    for(int i=0; i<=l; i++) tot = (tot + dp[n][1][i][2]) % MOD;
    cout<<tot;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:15:40: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     if (fopen("input.in", "r")) freopen("input.in", "r", stdin);
      |                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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