Submission #104700

#	Time	Username	Problem	Language	Result	Execution time	Memory
104700		the_art_of_war	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	374 ms	164088 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf_int = 1e9 + 100;
const ll inf_ll = 8e18;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double dbl;
#define pb push_back
const double pi = 3.1415926535898;
#define dout if(debug) cout
#define fi first
#define se second
#define sp setprecision
#define sz(a) (int(a.size()))
#define all(a) a.begin(),a.end()
bool debug = 0;
const int MAXN = 1e5 + 100;
const int LOG = 20;
const int mod = 1e9 + 7;
const int MX = 1e6 + 100;
typedef long long li;
const li MOD = 1000000000949747713ll;

int N,L;

int dp[101][1024][101][2][2];
int a[101];
ll get(int i,int cur_cost, int comp,int l,int r) {
    if(cur_cost > L)
        return 0;
    if(comp < 0)
        return 0;

    int next_cost = cur_cost;
    if(i > 0){
        next_cost += (a[i] - a[i-1] ) * (2*comp + l + r);
    }
    if(next_cost > L)
        return 0;
    if(i==N-1) {
        if(comp == 0)
            return 1;
        return 0;
    }


    if(dp[i][cur_cost][comp][l][r] != -1)
        return dp[i][cur_cost][comp][l][r];

    ll res = 0;
    res+=get(i+1,next_cost,comp-1,1,r) * comp; //left
    res+=get(i+1,next_cost,comp,1,r); //left

    res+=get(i+1,next_cost,comp-1,l,1) * comp; // right
    res+=get(i+1,next_cost,comp,l,1); // right

    res+=get(i+1,next_cost,comp+1,l,r); //new

    res+=get(i+1,next_cost,comp,l,r) * comp * 2; // to middle

    res+=get(i+1,next_cost,comp-1,l,r) * comp * (comp - 1);

    if(res)
    dout << i <<" "<<cur_cost <<" "<<comp <<" "<<l<<" "<<r<<" - "<<res<<endl;

    return dp[i][cur_cost][comp][l][r] = res%mod;
}

void solve() {
   memset(dp,-1,sizeof dp);
   cin >> N >> L;
   for(int i=0;i<N;++i){
       cin >> a[i];
   }
   sort(a,a+N);
   cout << get(0,0,0,0,0)<<"\n";

}

signed main() {
#ifdef zxc
    debug = 1;
    freopen("../input.txt", "r", stdin);
#else

#endif //zxc
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.setf(ios::fixed);
    cout.precision(20);

    int t = 1;

     while (t--)
         solve();
    dout << (1.0 * clock() / CLOCKS_PER_SEC)<<endl;
}

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