//new.cpp
/*
Author : Hocky Yudhiono
Kam 02 Mei 2019 04:13:03 WIB
Current Local Time : 16:13:03
getchar_unlocked > getchar > cin without sync > scanf > cin with sync
bool operator<(const MyStruct& rhs) const
On how to print Long Double to 5 decimal places :
printf("%.5Lf",ans);
On how to get random numbers :
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //For int
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); //For LL
cout << rng() << endl;
shuffle(isi.begin(),isi.end(),rng);
__gcd(a,b)
__builtin_ffs(a) first on bit
__builtin_clz(a) count leading zero
__builtin_ctz(a) count trailing zero
__builtin_popcount(a) numbers of on bits
*/
//#include <unordered_map>
//#include <unordered_set>
//#include <random>
//#include <chrono>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <cstdio>
#include <limits>
#include <string>
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
//using namespace __gnu_pbds;
using namespace std;
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize(3)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
// #pragma GCC diagnostic error "-fwhole-program"
// #pragma GCC diagnostic error "-fcse-skip-blocks"
// #pragma GCC diagnostic error "-funsafe-loop-optimizations"
// #pragma GCC diagnostic error "-std=c++14"
// #pragma GCC target ("string"...)
#pragma GCC push_options
#pragma GCC pop_options
#pragma GCC reset_options
#pragma GCC optimize ("O3")
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
// typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> pbds;
//If the time limit is strict, try not to use long double
#define fbo find_by_order
#define ook order_of_key
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define remove erase
//Remember to undefine if the problem is interactive
#define endl '\n'
#define DEBUG(X) cout << ">>> DEBUG(" << __LINE__ << ") " << #X << " = " << (X) << endl
const double eps = 1e-9;
const int INFMEM = 63;
const int INF = 1061109567;
const LL LINF = 4557430888798830399LL;
const double DINF = numeric_limits<double>::infinity();
const LL MOD = 1000000007;
const int dx[8] = {1,0,-1,0,1,1,-1,-1};
const int dy[8] = {0,1,0,-1,1,-1,1,-1};
const double PI = 3.141592653589793;
#ifdef _WIN32
#define getchar_unlocked getchar
#endif
#define GETCHAR getchar_unlocked
inline void fastll(LL &input_number)
{
input_number = 0;
int ch = GETCHAR();
int sign = 1;
while(ch < '0' || ch > '9'){
if(ch == '-') sign=-1;
ch = GETCHAR();
}
while(ch >= '0' && ch <= '9'){
input_number = (input_number << 3)+(input_number << 1) + ch-'0';
ch = GETCHAR();
}
input_number *= sign;
}
inline void open(string a){
freopen((a+".in").c_str(),"r",stdin);
freopen((a+".out").c_str(),"w",stdout);
}
inline void fasterios(){
//Do not use if interactive
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
}
LL n,k;
LL isi[15];
vector <LL> all;
LL memo[(1LL<<14)][2801];
//There are 6 cases
//Case 1 = 000
//Case 2 = 100
//Case 3 = 001
//Case 4 = 101
//Case 5 = |01
//Case 6 = |00
//Case 7 = 10|
//Case 8 = 00|
void add(LL &a,LL b){
a = (a+b)%MOD;
}
LL dp(LL mask, LL cnt){
LL pos = __builtin_popcountll(mask)+1;
// cout << pos << " " << mask << " " << cnt << endl;
if(pos > n && cnt <= k) return 1;
if(pos > n) return 0;
if(memo[mask][cnt+1400] != -1) return memo[mask][cnt+1400];
LL ret = 0;
for(int i = 0;i < n;i++){
if(mask&(1LL<<i)) continue;
//put pos in the (i+1)-th position
LL nxmask = (mask|(1LL<<i));
if(i == 0){
//left Wall case
if(mask&(1LL<<(i+1))){
//case 5
add(ret,dp(nxmask,cnt+isi[pos]));
}else{
//case 6
add(ret,dp(nxmask,cnt-isi[pos]));
}
}else if(i == n-1){
//Right wall case
if(mask&(1LL<<(i-1))){
//case 7
add(ret,dp(nxmask,cnt+isi[pos]));
}else{
//case 8
add(ret,dp(nxmask,cnt-isi[pos]));
}
}else{
//No wall case
//Case 1 = 000
//Case 2 = 100
//Case 3 = 001
//Case 4 = 101
bool kiri = (mask&(1LL<<(i-1)));
bool kanan = (mask&(1LL<<(i+1)));
if(kiri == 0 && kanan == 0){
//Case 1
add(ret,dp(nxmask,cnt-(2*isi[pos])));
}else if((kiri^kanan)){
//Case 2 and Case 3
add(ret,dp(nxmask,cnt));
}else{
//Case 4
add(ret,dp(nxmask,cnt+(2*isi[pos])));
}
}
}
return memo[mask][cnt+1400] = ret;
}
int main(){
memset(memo,-1,sizeof(memo));
cin >> n >> k;
for(int i = 1;i <= n;i++) cin >> isi[i];
sort(isi+1,isi+1+n);
if(n == 1) cout << 1 << endl;
else cout << dp(0,0) << endl;
return 0;
}
Compilation message
skyscraper.cpp:56:0: warning: ignoring #pragma comment [-Wunknown-pragmas]
#pragma comment(linker, "/stack:200000000")
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
575 ms |
359628 KB |
Output is correct |
| 2 |
Correct |
300 ms |
359544 KB |
Output is correct |
| 3 |
Correct |
302 ms |
359608 KB |
Output is correct |
| 4 |
Correct |
273 ms |
359576 KB |
Output is correct |
| 5 |
Correct |
302 ms |
359648 KB |
Output is correct |
| 6 |
Correct |
299 ms |
359512 KB |
Output is correct |
| 7 |
Correct |
315 ms |
359668 KB |
Output is correct |
| 8 |
Correct |
285 ms |
359492 KB |
Output is correct |
| 9 |
Correct |
323 ms |
359544 KB |
Output is correct |
| 10 |
Correct |
306 ms |
359544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
310 ms |
359672 KB |
Output is correct |
| 2 |
Correct |
637 ms |
359592 KB |
Output is correct |
| 3 |
Correct |
390 ms |
359524 KB |
Output is correct |
| 4 |
Correct |
633 ms |
359588 KB |
Output is correct |
| 5 |
Correct |
653 ms |
359592 KB |
Output is correct |
| 6 |
Correct |
490 ms |
359644 KB |
Output is correct |
| 7 |
Correct |
422 ms |
359600 KB |
Output is correct |
| 8 |
Correct |
402 ms |
359480 KB |
Output is correct |
| 9 |
Correct |
355 ms |
359644 KB |
Output is correct |
| 10 |
Correct |
651 ms |
359564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
575 ms |
359628 KB |
Output is correct |
| 2 |
Correct |
300 ms |
359544 KB |
Output is correct |
| 3 |
Correct |
302 ms |
359608 KB |
Output is correct |
| 4 |
Correct |
273 ms |
359576 KB |
Output is correct |
| 5 |
Correct |
302 ms |
359648 KB |
Output is correct |
| 6 |
Correct |
299 ms |
359512 KB |
Output is correct |
| 7 |
Correct |
315 ms |
359668 KB |
Output is correct |
| 8 |
Correct |
285 ms |
359492 KB |
Output is correct |
| 9 |
Correct |
323 ms |
359544 KB |
Output is correct |
| 10 |
Correct |
306 ms |
359544 KB |
Output is correct |
| 11 |
Correct |
310 ms |
359672 KB |
Output is correct |
| 12 |
Correct |
637 ms |
359592 KB |
Output is correct |
| 13 |
Correct |
390 ms |
359524 KB |
Output is correct |
| 14 |
Correct |
633 ms |
359588 KB |
Output is correct |
| 15 |
Correct |
653 ms |
359592 KB |
Output is correct |
| 16 |
Correct |
490 ms |
359644 KB |
Output is correct |
| 17 |
Correct |
422 ms |
359600 KB |
Output is correct |
| 18 |
Correct |
402 ms |
359480 KB |
Output is correct |
| 19 |
Correct |
355 ms |
359644 KB |
Output is correct |
| 20 |
Correct |
651 ms |
359564 KB |
Output is correct |
| 21 |
Incorrect |
327 ms |
359656 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
