Submission #112556

#TimeUsernameProblemLanguageResultExecution timeMemory
112556ckodserSkyscraper (JOI16_skyscraper)C++14
15 / 100
19 ms768 KiB
#include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector> #if __cplusplus >= 201103L #include <array> #include <atomic> #include <chrono> #include <condition_variable> #include <forward_list> #include <future> #include <initializer_list> #include <mutex> #include <random> #include <ratio> #include <regex> #include <scoped_allocator> #include <system_error> #include <thread> #include <tuple> #include <typeindex> #include <type_traits> #include <unordered_map> #include <unordered_set> #endif int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);} #define ll long long #define pb push_back #define ld long double #define mp make_pair #define F first #define S second #define pii pair<ll,ll> using namespace :: std; const ll mod=1e9+7; const ll maxn=110; const ll maxl=1010; inline void jam(ll &a,ll b){a+=b;if(a>=mod)a-=mod;} inline void jamz(ll &a,long long b,ll c){a+=(b*c)%mod;if(a>=mod)a-=mod;} inline ll ok(ll a){if(a>=mod)a-=mod;return a;} inline ll zarb(long long a,ll b){return (a*b)%mod;} ll a[maxn]; ll dp[maxn][maxn][maxl][4]; inline ll find_inp(ll out,ll t){ return out-(1^(t&1))+(1^(t>>1)); } int main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); ll n,l; cin>>n>>l; for(ll i=1;i<=n;i++){ cin>>a[i]; } sort(a+1,a+n+1); dp[0][0][0][3]=1; for(ll i=0;i<n;i++){ ll d=a[i+1]-a[i]; for(ll out=0;out<=i;out++){ for(ll u=0;u<=l;u++){ for(ll t=0;t<4;t++){ ll v=dp[i][out][u][t]; if(v==0)continue; ll inp=find_inp(out,t); ll inpmojaz=(inp-1)+(t>>1); ll outmojaz=(out-1)+(t&1); if(inpmojaz != outmojaz){exit(1);cout<<"WTF?!!";return 0;} ll uu=u+d*(inp+out); if(uu>l)continue; ll b; if(t==3 || t==0){ if(i==n-1){ b=zarb(out,inp); }else{ b=zarb(out,out-1); } } if(t==1 || t==2)b=ok(zarb(out,inp)-min(inp,out)+mod); jam(dp[i+1][out+1][uu][t],v); if(out)jamz(dp[i+1][out][uu][t],v,out); if(inp)jamz(dp[i+1][out][uu][t],v,inp); if(out && inp)jamz(dp[i+1][out-1][uu][t],v,b); if(i==n-1){ inpmojaz=inp; outmojaz=out; } if(t&1){ jamz(dp[i+1][out ][uu][t^1],v,inpmojaz); jam (dp[i+1][out+1][uu][t^1],v); } if(t&2){ if(out>=1)jamz(dp[i+1][out-1][uu][t^2],v,outmojaz); jam (dp[i+1][out ][uu][t^2],v); } } } } } ll ans=0; for(ll i=0;i<=l;i++){ jam(ans,dp[n][0][i][0]); } cout<<ans<<endl; }

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:72:47: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
 inline void jamz(ll &a,long long b,ll c){a+=(b*c)%mod;if(a>=mod)a-=mod;} 
                                             ~~^~~
skyscraper.cpp:105:9: note: 'b' was declared here
      ll b;
         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...