Submission #519277

#	Time	Username	Problem	Language	Result	Execution time	Memory
519277		Mukul202	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	172 ms	260648 KiB

skyscraper

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")

#include <bits/stdc++.h>
#define int long long
#define ld long double
#define all(x) x.begin(), x.end()
#define fr(i, n) for (int i = 0; i < (int)n; i++)
#define ff first
#define ss second
#define FILE                        \
  freopen("input.txt", "r", stdin); \
  freopen("output.txt", "w", stdout)
#define pb emplace_back // push_back
#define fio                         \
  ios_base::sync_with_stdio(false); \
  cin.tie(NULL);
#define ps(x, y) fixed << setprecision(y) << x
const int mod = 1000000007;
#define printclock cerr << "Time : " << 1000 * (ld)clock() / (ld)CLOCKS_PER_SEC << "ms\n";
using namespace std;

const int INF = 0x3f3f3f3f3f3f3f3f;

const int N = 1e2 + 5;
#define mod2 998244353

template <typename T>
using min_pq = priority_queue<T, std::vector<T>, greater<T>>;
#define pii pair<int, int>

template<class T,class F>
istream& operator>>(istream& is,pair<T,F>&p){
  is>>p.ff>>p.ss;
  return is;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v)
{
  for (auto &it : v)
    is >> it;
  return is;
}
template <typename... Args>
void in(Args &...args)
{
  ((cin >> args), ...);
}

template <class T, class U>
ostream &operator<<(ostream &os, pair<T, U> &p)
{
  os << p.ff << " " << p.ss;
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &x)
{
  for (auto &el : x)
    os << el << " ";
  return os;
}
template <typename... Args>
void out(Args... args)
{
  ((cout << args << " "), ...);
  cout << "\n";
}
// template<typename T>void out(T& x){for(auto&el :x)cout<<el<<" ";cout<<"\n";}
template <typename T, typename... Args>
std::string debug_detail(const char *names, T &&var, Args &&...args)
{
  std::stringstream builder;
  const char *end = names;
  while (*end != ',' && *end != '\0')
    ++end;
  (builder).write(names, end - names) << '=' << var;
  if constexpr (sizeof...(Args) > 0)
  {
    (builder << ", ") << debug_detail(end + 1, std::forward<Args>(args)...);
  }
  return builder.str();
}
template <typename... Args>
void debug_entry(const char *names, Args &&...args)
{
  std::stringstream retval;
  retval << "[" << debug_detail(names, std::forward<Args>(args)...) << "]\n";
  std::cout << retval.str();
}
#define deb(...) debug_entry(#__VA_ARGS__, __VA_ARGS__)

int n,k;
vector<int>a;
int dp[N][N][1005][3];

int f(int i,int c,int sum,int ends){
  if(sum>k || ends>2)
    return 0LL;
  if(c==0 && i>1)
    return 0LL;
  if(i==n+1)
    return ends==2 && c==1;
  int& ret=dp[i][c][sum][ends];
  if(ret!=-1LL)
    return ret;
  int ans=0LL;
  int nsum=sum+(a[i]-a[i-1])*(2*c-ends);
  //case merge component
  if(c>=2)
    ans+=1ll*(c-1)*f(i+1,c-1,nsum,ends);
  if(c>=1)//append to one end of any component
    ans+=1ll*(2*c-ends)*f(i+1,c,nsum,ends);
  ans+=1LL*(c+1-ends)*f(i+1,c+1,nsum,ends);//create new component
  if(ends<2)//append to end and create a new component
    ans+=1LL*(2-ends)*f(i+1,c+1,nsum,ends+1);
  if(ends<2)//no need to create a new component
    ans+=1ll*(2-ends)*f(i+1,c,nsum,ends+1);
  ans%=mod;
  return ret=ans;
}

inline void solve()
{ 
  in(n,k);
  a.resize(n+1);
  for(int i=1;i<=n;++i)
    cin>>a[i];
  if(n==1){
    out(1);
    return ;
  }
  sort(all(a));
  memset(dp,-1LL,sizeof(dp));
  out(f(1,0,0,0));
}

inline void solve2()
{
  
}

inline void solve3()
{
  
}

int32_t main()
{
  fio;

  int t = 1;
  // cin >> t;
  fr(j, t)
  {
    // cout<<"Case #"<<j+1<<":  ";
    solve();
  }

  printclock;
  return 0;
}

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