Facebook
From faiyazsadi, 2 Weeks ago, written in C++.
Embed
Download Paste or View Raw
Hits: 151
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. void solve() {
  9.     int n;
  10.     cin >> n;
  11.     vector<int> a(n);
  12.     for(int i = 0; i < n; ++i) {
  13.         cin >> a[i];
  14.     }
  15.     int ans = -1;
  16.     for(int i = 0; i < n; ++i) {
  17.         vector<int> indicies;
  18.         for(int j = 0; j < n; ++j) {
  19.             if(i != j) {
  20.                 indicies.push_back(j);
  21.             }
  22.         }
  23.         do {
  24.             vector<bool> taken(n, false);
  25.             int sum = 0;
  26.             for(int k = 0; k < (int) indicies.size(); ++k) {
  27.                 taken[indicies[k]] = true;
  28.                 int l = indicies[k] - 1;
  29.                 int r = indicies[k] + 1;
  30.                 while(l >= 0 and taken[l] == true) {
  31.                     l -= 1;
  32.                 }
  33.                 while(r < n and taken[r] == true) {
  34.                     r += 1;
  35.                 }
  36.                 if(l < 0 and r >= n) {
  37.                     sum += a[indicies[k]];
  38.                 } else if(l >= 0 and r >= n) {
  39.                     sum += a[l];
  40.                 } else if(l < 0 and r < n) {
  41.                     sum += a[r];
  42.                 } else {
  43.                     sum += a[l] * a[r];
  44.                 }
  45.             }
  46.             sum += a[i];
  47.             ans = max(ans, sum);
  48.  
  49.         } while(next_permutation(indicies.begin(), indicies.end()));
  50.     }
  51.    
  52.     cout << ans << 'n';
  53. }
  54.  
  55. int main() {
  56.     /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
  57.    int t;
  58.    cin >> t;
  59.    while(t--) {
  60.        cout << "#" << t + 1 << ' ';
  61.        solve();
  62.    }
  63.     return 0;
  64. }
  65.  
  66.  
  67. /*
  68.  
  69. 10
  70. 9
  71. 1 2 3 4 5 6 7 8 9
  72. 9
  73. 1 2 3 4 5 6 7 8 9
  74. 9
  75. 1 2 3 4 5 6 7 8 9
  76. 9
  77. 1 2 3 4 5 6 7 8 9
  78. 9
  79. 1 2 3 4 5 6 7 8 9
  80. 9
  81. 1 2 3 4 5 6 7 8 9
  82. 9
  83. 1 2 3 4 5 6 7 8 9
  84. 9
  85. 1 2 3 4 5 6 7 8 9
  86. 9
  87. 1 2 3 4 5 6 7 8 9
  88. 9
  89. 1 2 3 4 5 6 7 8 9
  90.  
  91. */
  92.  
  93.  
  94. /*
  95.  
  96. 10
  97. 10
  98. 1 2 3 4 5 6 7 8 9 10
  99. 10
  100. 1 2 3 4 5 6 7 8 9 10
  101. 10
  102. 1 2 3 4 5 6 7 8 9 10
  103. 10
  104. 1 2 3 4 5 6 7 8 9 10
  105. 10
  106. 1 2 3 4 5 6 7 8 9 10
  107. 10
  108. 1 2 3 4 5 6 7 8 9 10
  109. 10
  110. 1 2 3 4 5 6 7 8 9 10
  111. 10
  112. 1 2 3 4 5 6 7 8 9 10
  113. 10
  114. 1 2 3 4 5 6 7 8 9 10
  115. 10
  116. 1 2 3 4 5 6 7 8 9 10
  117.  
  118. */