fork(2) download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. using bs = unsigned long long;
  4. using pi = pair<int, int>;
  5. const int MAXN = 100005;
  6.  
  7. int chk[MAXN];
  8. bs msk[2000];
  9.  
  10. void upload(int s, int l){
  11. 	auto get_slowa = [&](int s, int l){
  12. 		bs ret = 0;
  13. 		ret |= (msk[s >> 6] >> (s & 63));
  14. 		if(s & 63){
  15. 			auto fu = msk[(s >> 6) + 1] & ((1ull << (s & 63)) - 1ull);
  16. 			ret |= (fu << (64 - (s & 63)));
  17. 		}
  18. 		if(l < 64) ret &= (1ull << l) - 1ull;
  19. 		return ret;
  20. 	};
  21. 	for(int i=0; i<l; i+=64){
  22. 		auto slowa = get_slowa(s + i, min(64, l - i));
  23. 		msk[i >> 6] |= slowa;
  24. 	}
  25. }
  26.  
  27. int main(){
  28. 	int n; scanf("%d",&n);
  29. 	int minv = 1e9;
  30. 	for(int i=0; i<n; i++){
  31. 		int x; scanf("%d",&x);
  32. 		minv = min(minv, x);
  33. 		chk[x]++;
  34. 	}
  35. 	if(chk[minv] == 1){
  36. 		cout << minv << endl;
  37. 		return 0;
  38. 	}
  39. 	for(int i=100000; i>minv; i--){
  40. 		if(chk[i] == 0) continue;
  41. 		for(int j=i; j<=100000; j+=i){
  42. 			upload(j, min(i, 100001 - j));
  43. 		}
  44. 		msk[i >> 6] |= (1ull << (i & 63)); 
  45. 	}
  46. 	int ret = 0;
  47. 	for(int i=100000; i>=0; i--){
  48. 		if((msk[i >> 6] >> (i & 63)) & 1){
  49. 			ret = max(ret, i % minv);
  50. 		}
  51. 	}
  52. 	cout << ret << endl;
  53. }
  54.  
  55.  
Time limit exceeded #stdin #stdout 5s 15640KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/XGSZaC
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!