Submission #519277

#TimeUsernameProblemLanguageResultExecution timeMemory
519277Mukul202Skyscraper (JOI16_skyscraper)C++17
100 / 100
172 ms260648 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...