제출 #602270

#제출 시각아이디문제언어결과실행 시간메모리
602270EvirirSkyscraper (JOI16_skyscraper)C++17
100 / 100
410 ms130364 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> using namespace std; //using namespace __gnu_pbds; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #define watch(x) cout<<(#x)<<"="<<(x)<<'\n' #define mset(d,val) memset(d,val,sizeof(d)) #define cbug if(DEBUG) cout #define setp(x) cout<<fixed<<setprecision(x) #define sz(x) (int)(x).size() #define all(x) begin(x), end(x) #define forn(i,a,b) for(int i=(a);i<(b);i++) #define fore(i,a,b) for(int i=(a);i<=(b);i++) #define pb push_back #define F first #define S second #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef long double ld; typedef pair<ll,ll> ii; typedef vector<ll> vi; typedef vector<ii> vii; //template<typename T> //using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; void SD(int t=0){ cout<<"PASSED "<<t<<endl; } ostream& operator<<(ostream &out, ii x){ out<<"("<<x.F<<","<<x.S<<")"; return out; } template<typename T> void amax(T &a, T b){ a=max(a,b); } template<typename T> void amin(T &a, T b){ a=min(a,b); } const ll INF = ll(1e18); const int MOD = 1e9+7; const bool DEBUG = 0; const int MAXN = 105; const int MAXA = 1005; const int LG = 21; ll add(ll a, ll b, ll m = MOD) { a+=b; if(abs(a)>=m) a%=m; if(a<0) a+=m; return a; } ll mult(ll a, ll b, ll m = MOD) { if(abs(a)>=m) a%=m; if(abs(b)>=m) b%=m; a*=b; if(abs(a)>=m) a%=m; if(a<0) a+=m; return a; } inline void radd(ll &a, ll b) { a = add(a, b); } ll n,L; ll a[MAXN]; ll dp[MAXN][MAXN][MAXA][3]; // current num%2, # of cc, sum, front done + back done int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>L; fore(i,1,n) cin>>a[i]; sort(a+1,a+n+1); // special case: can use up front and back at the same time if(n==1) { cout<<1<<'\n'; return 0; } dp[0][0][0][0] = 1; fore(i,1,n) { fore(j,1,n) fore(k,0,L) { ll val = a[i] - a[i-1]; ll inc; // --- put front/back --- fore(l,1,2) { // new cc inc=((j-1)*2-(l-1))*val; if(inc>=0 && k-inc>=0) radd(dp[i][j][k][l], mult(2-(l-1), dp[i-1][j-1][k-inc][l-1])); // extend cc inc=(j*2-(l-1))*val; if(inc>=0 && k-inc>=0) radd(dp[i][j][k][l], mult(2-(l-1), dp[i-1][j][k-inc][l-1])); } // --- put middle --- fore(l,0,2) { // new cc inc=((j-1)*2-l)*val; if(inc>=0 && k-inc>=0) radd(dp[i][j][k][l], mult((j-1)+1-l, dp[i-1][j-1][k-inc][l])); // extend cc inc=(j*2-l)*val; if(inc>=0 && k-inc>=0) radd(dp[i][j][k][l], mult(j*2-l, dp[i-1][j][k-inc][l])); // merge cc inc=((j+1)*2-l)*val; if(inc>=0 && k-inc>=0) radd(dp[i][j][k][l], mult((j+1)-1, dp[i-1][j+1][k-inc][l])); } } } ll ans=0; fore(k,0,L) radd(ans, dp[n][1][k][2]); cout<<ans<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...