fork download
copy 
  1. // cas O(N+1!)
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <tr1/unordered_set>
  6. using namespace std;
  7. using namespace std::tr1;
  8.  
  9. int main() {
  10. 	int T;
  11. 	scanf(" %d",&T);
  12. 	for(int t =0; t < T; t++) {int N,odp =0;
  13. 	scanf(" %d",&N);
  14. 	vector<int> d(N);
  15. 	for(int i =0; i < N; i++) scanf(" %d",&d[i]);
  16.  
  17. 	vector<int> p(N);
  18. 	for(int i =0; i < N; i++) p[i] =i;
  19. 	// skusim vsetky permutacie
  20. 	while(true) {
  21. 		unordered_set<int> casy; // kedy koncia filmy v sale 1
  22. 		casy.insert(d[p[0]]);
  23. 		int sum1 =d[p[0]];
  24. 		// vezmem sekeru a rozrubem permutaciu na 2 casti
  25. 		for(int i =1; i < N; i++) {
  26. 			// prva cast, i filmov do saly 1, druha do saly 2
  27. 			// zratam pocet prestupov
  28. 			int odp0 =0,sum2 =0;
  29. 			for(int j =i; j < N; j++) {
  30. 				sum2 +=d[p[j]];
  31. 				if(casy.count(sum2)) odp0++;}
  32. 			odp =max(odp,odp0);
  33. 			casy.insert(sum1+d[p[i]]);
  34. 			sum1 +=d[p[i]];}
  35. 		if(!next_permutation(p.begin(),p.end())) break;}
  36. 	printf("Vstup %d: %d\n",t+1,odp);}
  37. 	return 0;}
Success #stdin #stdout 0.06s 2968KB
comments (?)
stdin
copy 
3
4
10 20 20 30
6
10 20 20 20 40 30
8
20 30 40 50 60 70 80 10
stdout
copy 
Vstup 1: 1
Vstup 2: 2
Vstup 3: 2
https://ideone.com/cC41E
language:
C++14 (gcc 8.3)
created:
12 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!