Submission #1301956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301956		davele	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	106 ms	110016 KiB

skyscraper

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define vi vector <int>
#define pq priority_queue
#define MASK(i) (1ll<<(i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define x0 ___x0
#define y0 ___y0
#define div   ___div
#define next   ___next
#define prev   ___prev
#define left   ___left
#define right   ___right
#define pos pisosi
#define pb push_back
#define pf push_front
using namespace std;

const int mod = 1e9+7;
void add (int &a, const int&b){
    a+=b;
    if (a>=mod) a-=mod;
}

void sub (int&a, const int&b){
    a-=b;
    if (a<0) a+=mod;
}

void mul (int&a, const int&b){
    a*=b;
    a%=mod;
}

template<class X, class Y>
    bool minimize(X &x, const Y&y){
        if (x<=y) return false;
        else{
            x = y;
            return true;
        }
    }
template<class X, class Y>
    bool maximize (X &x, const Y&y){
        if (x>=y) return false;
        else{
            x = y;
            return true;
        }
    }

/////////////////////////////////////////////////////////////////////////////////

//// dang nhap ham
//#ifndef davele
//
//#endif // davele
//
//// chay thu ham main:
//
//#ifdef davele
//
//#endif // davele

////////////////////////////////////////////////////////////////////////////
//const int lim = , limit = , inf = ;
const string name = "skyscraper";

int n, A[10005], maxdiff;
int dp[101][1001][101][3];

void process(){
    if (n==1){
        cout<<"1";
        return;
    }
    sort (A+1, A+n+1);
    // dp[i][j][k][z]
    // = so hoan vi sao cho sau khi them thang thu i vao
    // , va co different = j (cac thang dang trong thi mang gia tri la A[i])
    // , co so tplt la k
    // va tong so luong dau chua dung la z
    // constrain : k<=i
    // z<=2
    // j<=maxdiff
    // i<=n
    dp[0][0][0][2] = 1;
    for (int i=0; i<n; i++){
        for (int j=0; j<=maxdiff; j++){
            for (int k=0; k<=i; k++){
                for (int z = 0; z<=2; z++){
                    if (dp[i][j][k][z]==0) continue;
                    int cur = dp[i][j][k][z];
                    int rem = n-i;
                    int emptyscc = k-1+z;
                    int delta = (k*2-(2-z))*(A[i+1]-A[i]); // cac gia tri trong doi tu A[i] -> A[i+1]
                    int newj = j+delta;
                    if (newj>maxdiff || rem<emptyscc || emptyscc==0) continue;
//                    if (newj==17) cerr<<i<<" "<<j<<" "<<k<<" "<<z<<" "<<cur<<"\n";
//                    if (k==0 && z<2) cerr<<i<<" "<<j<<" "<<k<<" "<<z<<" "<<cur<<" "<<delta<<"\n";
                    // case 1: tao ra mot tplt moi (khong duoc cham vao bien)
                    if (rem-emptyscc>=2) add (dp[i+1][newj][k+1][z], cur*emptyscc%mod);
                    // case 2: tao ra mot tplt moi (cham vao bien)
                    if (rem-emptyscc>=1 && z>0) add (dp[i+1][newj][k+1][z-1], z*cur%mod);
                    // case 3: ket noi bien va tplt
                    if (z>0 && k>0) add (dp[i+1][newj][k][z-1], z*cur%mod);
                    // case 4: ket noi 2 tplt
                    if (k>1) add (dp[i+1][newj][k-1][z], (k-1)*cur%mod);
                    // case 5: them vao sau hoac truoc mot tplt
                    if (rem-emptyscc>=1 && 2*k-(2-z)>=1) add (dp[i+1][newj][k][z], (2*k - (2-z))*cur%mod);
                }
            }
        }
    }
    int ret = 0;
    for (int diff = 0; diff<=maxdiff; diff++){
//        cerr<<diff<<" "<<dp[n][diff][1][0]<<"\n";
        add (ret, dp[n][diff][1][0]);
    }
    cout<<ret;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //
    if (fopen((name+".inp").c_str(), "r")){
        freopen ((name+".inp").c_str(), "r", stdin);
        freopen ((name+".out").c_str(), "w", stdout);
    }
    //
    cin>>n>>maxdiff;
    for (int i=1; i<=n; i++) cin>>A[i];
    process();
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:132:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         freopen ((name+".inp").c_str(), "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:133:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen ((name+".out").c_str(), "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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