Submission #333816

#	Time	Username	Problem	Language	Result	Execution time	Memory
333816		nextgenxing	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	69 ms	25452 KiB

skyscraper

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

typedef long long ll;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define F0R(i, x) FOR(i, 0, x)
const int MAX_N = 102;
const int MAX_L = 1002;
const ll MOD = 1000000007;

void setIO(string name = "skyscraper") {
    ios_base::sync_with_stdio(0); cin.tie(0);
    freopen((name+".in").c_str(), "r", stdin);
    freopen((name+".out").c_str(), "w", stdout);
}

ll ad(ll& a, ll b, ll mod = MOD){
    a = (a+b)%mod; return a;
}

int n, l;
ll dp[MAX_N][MAX_N][MAX_L][3], a[MAX_N];

int main(int argc, const char * argv[]) {
//    setIO();
    cin >> n >> l; F0R(i, n) cin >> a[i];
    sort(a, a+n), a[n] = 10001;
    if(n == 1){ cout << 1 << endl; return 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;
    FOR(i, 1, n) FOR(j, 1, i+1) F0R(k, l+1) F0R(z, 3) if(dp[i][j][k][z]){
        int d = a[i+1]-a[i];
        // add to end
        if(z < 2 && k+d*(2*j-z-1) <= l) ad(dp[i+1][j][k+d*(2*j-z-1)][z+1], (2-z)*dp[i][j][k][z]); // add to cc
        if(z < 2 && k+d*(2*j-z+1) <= l) ad(dp[i+1][j+1][k+d*(2*j-z+1)][z+1], (2-z)*dp[i][j][k][z]); // make new cc
        // add to middle
        if(k+d*(2*j-z) <= l) ad(dp[i+1][j][k+d*(2*j-z)][z], (2*j-z)*dp[i][j][k][z]); // add to cc
        if(k+d*(2*j-z+2) <= l) ad(dp[i+1][j+1][k+d*(2*j-z+2)][z], (j-z+1)*dp[i][j][k][z]); // make new cc
        if(j && k+d*(2*j-z-2) <= l) ad(dp[i+1][j-1][k+d*(2*j-z-2)][z], (j-1)*dp[i][j][k][z]); // merge 2 ccs
    }
    ll ans = 0; F0R(i, l+1) ad(ans, dp[n][1][i][2]);
    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'void setIO(std::string)':
skyscraper.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   13 |     freopen((name+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   14 |     freopen((name+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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