Submission #104699

#TimeUsernameProblemLanguageResultExecution timeMemory
104699the_art_of_warSkyscraper (JOI16_skyscraper)C++14
20 / 100
380 ms164088 KiB
#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]; int 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...