Submission #1116758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116758		Tai_xiu	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	50 ms	3124 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define i128 int128
#define ii pair<int,int>
#define ld long double
#define vi vector<int>
#define vvi vector<vi>
#define vii vector<pair<int,int>>
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FOR1(i,a,b,c) for (int i=a;i<=b;i+=c)
#define REP(i,a,b) for (int i=a;i>=b;i--)
#define REP1(i,a,b,c) for(int i=b;i>=a;i-=c)
#define endh '\n';
#define len(a) a.length()
#define pb(c) push_back(c)
#define elif else if
#define ppb() pop_back()
#define rong std::npos
#define all(c) (c.begin(),c.end())
#define Z int
#define R double
#define lcm(a,b) ((int) (a/__gcd(a,b))*b)
#define mk(a,b) make_pair(a,b)
Z dx4[]={-1,1,0,0};
Z dy4[]={0,0,1,-1};
string co="YES",khong="NO";
const int mod=1e9+7;
Z dp[2][103][1003][4];
Z a[103];
Z n,L;
Z add (Z a,Z b)
{
    a%=mod;
    b%=mod;
    a+=b;
    return a%mod;
}
/*
1 1
1
*/
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    dp[1][1][0][0]=1;
    dp[1][1][0][1]=2;
    cin>>n>>L;
    FOR(i,1,n) cin>>a[i];
     if (n == 1) return cout << 1 << '\n', 0;
    sort(a+1,a+n+1);
    FOR(i,2,n){
        Z curr=(i&1);
        Z prev=(curr^1);
        FOR(cc,1,n){
            FOR(sum,0,L){
                FOR(bien,0,2){
                    Z val=dp[prev][cc][sum][bien];
                    Z newsum=(2*cc-bien)*(a[i]-a[i-1])+sum;
                    if (val==0) continue;
                    if (newsum<=L) {
                        // them 1 tplt
                        {


                        dp[curr][cc+1][newsum][bien]= add(dp[curr][cc+1][newsum][bien],(cc+1-bien)*val);
                        dp[curr][cc+1][newsum][bien+1]=add(dp[curr][cc+1][newsum][bien+1],(2-bien)*val);
                        }
                        // them vao 1 tplt
                        {

                        dp[curr][cc][newsum][bien]=add(dp[curr][cc][newsum][bien],(2*cc-bien)*val);
                        dp[curr][cc][newsum][bien+1]=add(dp[curr][cc][newsum][bien+1],(2-bien)*val);
                        }
                        // gop
                        {

                        dp[curr][cc-1][newsum][bien]=add(dp[curr][cc-1][newsum][bien],(cc-1)*val);
                        }
                    }
                    dp[prev][cc][sum][bien]=0;
                }
            }
        }

    }
    Z ans=0;
    FOR(i,0,L) ans=add(ans,dp[n&1][1][i][2]);
    cout<<ans;
}

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