fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long S[] = {2, 7, 13, 20, 59, 66, 243, 250, 979, 986, 3923, 3930, 15699, 15706, 62803, 62810, 251219, 251226, 1004883, 1004890, 4019539, 4019546, 16078163, 16078170, 64312659, 64312666, 257250643, 257250650, 1029002579, 1029002586, 4116010323, 4116010330};
  5. const long long Z[] = {2, 9, 22, 42, 101, 167, 410, 660, 1639, 2625, 6548, 10478, 26177, 41883, 104686, 167496, 418715, 669941, 1674824, 2679714, 6699253, 10718799, 26796962, 42875132, 107187791, 171500457, 428751100, 686001750, 1715004329, 2744006915, 6860017238, 10976027568};
  6.  
  7. bool recur(int i, long long s) {
  8. 	if(s==0)
  9. 		return true;
  10. 	if(i<0 || s<0 || s>Z[i])
  11. 		return false;
  12. 	int j = i-1;
  13. 	while(j>0 && S[j]>s-S[i]) j--;
  14. 	bool b = recur(j, s-S[i]);
  15. 	if(!b) b = recur(i-1, s);
  16. 	return b;
  17. }
  18.  
  19. int main() {
  20. 	int T;
  21. 	long long N;
  22. 	cin >> T;
  23. 	while(T--) {
  24. 		cin >> N;
  25. 		cout << (recur(31, N) ? "YES\n" : "NO\n");
  26. 	}
  27. 	return 0;
  28. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
2
9 
11
stdout
copy 
YES
NO
https://ideone.com/bEgbvM
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!