Submission #403032

#	Time	Username	Problem	Language	Result	Execution time	Memory
403032		AmdSadi	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	510 ms	383048 KiB

skyscraper

#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]);
      |             ^~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80