oj.uz

Submission #403032

# Submission time Handle Problem Language Result Execution time Memory
403032 2021-05-12T16:56:29 Z AmdSadi Skyscraper (JOI16_skyscraper) C++17
100 / 100
 510 ms 383048 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 382880 KB Output is correct
2 Correct 155 ms 382940 KB Output is correct
3 Correct 162 ms 382868 KB Output is correct
4 Correct 156 ms 382960 KB Output is correct
5 Correct 155 ms 382864 KB Output is correct
6 Correct 155 ms 382856 KB Output is correct
7 Correct 154 ms 382848 KB Output is correct
8 Correct 153 ms 382916 KB Output is correct
9 Correct 155 ms 382980 KB Output is correct
10 Correct 153 ms 382908 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 382916 KB Output is correct
2 Correct 155 ms 382860 KB Output is correct
3 Correct 156 ms 382884 KB Output is correct
4 Correct 155 ms 382844 KB Output is correct
5 Correct 155 ms 382920 KB Output is correct
6 Correct 157 ms 382928 KB Output is correct
7 Correct 153 ms 382884 KB Output is correct
8 Correct 154 ms 382916 KB Output is correct
9 Correct 154 ms 382840 KB Output is correct
10 Correct 152 ms 382904 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 382880 KB Output is correct
2 Correct 155 ms 382940 KB Output is correct
3 Correct 162 ms 382868 KB Output is correct
4 Correct 156 ms 382960 KB Output is correct
5 Correct 155 ms 382864 KB Output is correct
6 Correct 155 ms 382856 KB Output is correct
7 Correct 154 ms 382848 KB Output is correct
8 Correct 153 ms 382916 KB Output is correct
9 Correct 155 ms 382980 KB Output is correct
10 Correct 153 ms 382908 KB Output is correct
11 Correct 155 ms 382916 KB Output is correct
12 Correct 155 ms 382860 KB Output is correct
13 Correct 156 ms 382884 KB Output is correct
14 Correct 155 ms 382844 KB Output is correct
15 Correct 155 ms 382920 KB Output is correct
16 Correct 157 ms 382928 KB Output is correct
17 Correct 153 ms 382884 KB Output is correct
18 Correct 154 ms 382916 KB Output is correct
19 Correct 154 ms 382840 KB Output is correct
20 Correct 152 ms 382904 KB Output is correct
21 Correct 156 ms 382824 KB Output is correct
22 Correct 510 ms 382936 KB Output is correct
23 Correct 454 ms 383000 KB Output is correct
24 Correct 433 ms 382832 KB Output is correct
25 Correct 461 ms 383048 KB Output is correct
26 Correct 387 ms 382916 KB Output is correct
27 Correct 251 ms 383012 KB Output is correct
28 Correct 272 ms 382988 KB Output is correct
29 Correct 430 ms 382856 KB Output is correct
30 Correct 494 ms 382940 KB Output is correct