Submission #403032

#TimeUsernameProblemLanguageResultExecution timeMemory
403032AmdSadiSkyscraper (JOI16_skyscraper)C++17
100 / 100
510 ms383048 KiB
#include<bits/stdc++.h> using namespace std; #define SPEED ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define READ freopen("in.txt","r",stdin) #define WRITE freopen("out.txt","w",stdout); #define pb push_back #define mem(arr,val) memset(arr,val,sizeof(arr)) #define sf(x) scanf("%d",&x) #define sf2(x,y) scanf("%d %d",&x,&y) #define sf3(x,y,z) scanf("%d %d %d",&x,&y,&z) #define sl(x) scanf("%lld",&x) #define sl2(x,y) scanf("%lld %lld",&x,&y) #define sl3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z) #define sd(x) scanf("%lf",&x); #define pii pair<int,int> #define pLL pair<long long,long long> #define pDB pair<double,double> #define ff first #define sn second #define PRINT_CASE printf("Case %d: ",tc++) #define PRINT_CASENL printf("Case %d:\n",tc++) #define lnd tree[ind<<1] #define rnd tree[(ind<<1)+1] #define cnd tree[ind] #define lndp b,(b+e)>>1,(ind<<1) #define rndp ((b+e)>>1)+1,e,(ind<<1)+1 #define IN(a,x,y) (a>=x && a<=y) #define popcountL __builtin_popcountll #define popcount __builtin_popcount #define endl "\n" /// int other=mask^((1<<n)-1); typedef long long ll; typedef long long LL; typedef long long int lln; typedef unsigned long long int ull; //typedef long long lld; //const double pi=acos(-1.0); int fx[]={1,-1,0,0}; //direction array int fy[]={0,0,1,-1}; int dir[4][2]={1,0,-1,0,0,-1,0,1}; //int X[8]={0,0,1,-1,-1,1,1,-1}; //int Y[8]={1,-1,0,0,-1,-1,1,1}; int knight[8][2]={1,2,1,-2,2,1,2,-1,-1,2,-1,-2,-2,1,-2,-1}; const long double EPS=1e-9; //#define INF 10000 ll lcm(ll a,ll b) { return ((a*b)/__gcd(a,b)); } //struct compare //{ // bool operator()(const pLL& l, const pLL& r) // { //// if(l.ff==r.ff) //// { //// return l.sn<r.sn; //// } // return l.sn>r.sn; //// if(l.ff==r.ff) //// { //// return l.sn>rnd; //// } // } //}; ll INF=1e18; //const int mod=998244353; const int mod=1000000007; // Including Policy Based DS //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //using namespace __gnu_pbds; //typedef tree<pii,null_type,less<pii >,rb_tree_tag,tree_order_statistics_node_update>ordered_set; //ordered_set X; //////cout<<*X.find_by_order(1)<<endl; ////cout<<X.order_of_key(-5)<<endl; //4352348930241 //const int mod=11092019; //struct HASH{ // size_t operator()(const pair<int,int>&x)const{ // return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32)); // } //}; //unordered_map<pair<int,int>,pair<int,int>,HASH>parent; //unordered_map<pair<int,int>,int,HASH>sizee; typedef pair<pair<int,int > ,int> pair3; struct compare { bool operator()(const pair<int,pii>& l, const pair<int,pii>& r) { return l.ff>r.ff; } }; ///code goes from here const int mx=300010; int arr[mx]; int n,L; ll dp[110][1010][110][2][2]; ll fun(int pos,int cost,int component,int prefix,int suffix) { if(component<0) return 0; if(pos) { cost+=(arr[pos]-arr[pos-1])*(2*component+prefix+suffix); } if(cost>L) return 0; if(pos==n-1) { if(component==0) return 1; return 0; } ll &ret=dp[pos][cost][component][prefix][suffix]; if(ret!=-1) return ret; ret=0; ret+=fun(pos+1,cost,component,1,suffix); ret+=fun(pos+1,cost,component,prefix,1); ret+=fun(pos+1,cost,component+1,prefix,suffix); ret+=(fun(pos+1,cost,component-1,prefix,suffix)*(component)*(component-1)); ret+=(fun(pos+1,cost,component,prefix,suffix)*component*2); ret+=fun(pos+1,cost,component-1,1,suffix)*component; ret+=fun(pos+1,cost,component-1,prefix,1)*component; ret%=mod; return ret; } int main() { //SPEED; // READ; // WRITE; int t=1,tc=1; // sf(t); while(t--) { sf2(n,L); for(int i=0;i<n;i++) { sf(arr[i]); } sort(arr,arr+n); mem(dp,-1); cout<<fun(0,0,0,0,0)<<endl; } return 0; }

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:139:13: warning: unused variable 'tc' [-Wunused-variable]
  139 |     int t=1,tc=1;
      |             ^~
skyscraper.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define sf2(x,y) scanf("%d %d",&x,&y)
      |                  ~~~~~^~~~~~~~~~~~~~~
skyscraper.cpp:143:9: note: in expansion of macro 'sf2'
  143 |         sf2(n,L);
      |         ^~~
skyscraper.cpp:8:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define sf(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
skyscraper.cpp:146:13: note: in expansion of macro 'sf'
  146 |             sf(arr[i]);
      |             ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...