Submission #1258905

#TimeUsernameProblemLanguageResultExecution timeMemory
1258905hamanp87Skyscraper (JOI16_skyscraper)C++20
100 / 100
86 ms77124 KiB
#include<bits/stdc++.h> using namespace std; using ll=long long; //#pragma GCC optimize("03,unroll-loops") //#pragma GCC target("avx2") //#pragma GCC target("sse4") #define all(v) v.begin(),v.end() #define F first #define S second #define pub push_back #define pob pop_back #define puf push_front #define pof pop_front //#define randi uniform_int_distribution<long long> #define damoon(v) v.resize(unique(all(v))-v.begin()) //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //randi dist(0,10000000000000000); typedef pair<int,int> pii; typedef pair<long long,long long> pll; typedef pair<int,bool> pib; typedef pair<long long,bool> plb; typedef pair<int,pii> pip; typedef pair<pii,int> ppi; typedef vector<int> veci; typedef vector<long long> vecl; typedef vector<bool> vecb; typedef vector<pii> vecp; typedef set<int> seti; typedef set<long long> setl; typedef set<pii> setp; typedef map<int,int> mapii; typedef map<long long,long long> mapll; typedef map<int,bool> mapib; typedef map<long long,bool> maplb; const int inf=1e9,neginf=-1e9; const ll mod=1000000007LL; const double PI=acos(-1); int a[105]; ll dp[105][105][1005][3]; void solve() { int n,L; cin>>n>>L; for(int i=1;i<=n;i++) cin>>a[i]; if(n==1) { cout<<"1\n"; return; } sort(a+1,a+n+1); a[n+1]=10000; dp[0][0][0][0]=1; for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) { for(int k=0;k<=L;k++) { for(int m=0;m<3;m++) { int dif=(2*j-m)*(a[i+1]-a[i]); if(dif>k) continue; int prvk=k-dif; ll wys=0; wys+=dp[i-1][j-1][prvk][m]; if(m>0) wys+=((3-m)*dp[i-1][j-1][prvk][m-1]); wys+=((2*j-m)*dp[i-1][j][prvk][m]); if(m==1) { wys+=(2LL*j*dp[i-1][j][prvk][m-1]); } else if(m==2) { if(i==n) { wys+=dp[i-1][j][prvk][m-1]; } else if(j>1) { wys+=((ll)(j-1)*dp[i-1][j][prvk][m-1]); } } if(m==2) { if(i==n) { wys+=dp[i-1][j+1][prvk][m]; } else { wys+=((ll)j*(j-1)*dp[i-1][j+1][prvk][m]); } } else if(m==1) { wys+=((ll)j*j*dp[i-1][j+1][prvk][m]); } else { wys+=((ll)j*(j+1)*dp[i-1][j+1][prvk][m]); } dp[i][j][k][m]=(dp[i][j][k][m]+wys)%mod; } } } } ll ans=0; for(int k=0;k<=L;k++) ans=(ans+dp[n][1][k][2])%mod; cout<<ans<<"\n"; } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); //ifstream fin("in.txt"); //ofstream fout("out.txt"); int t=1; //cin>>t; while(t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...