fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define fi first
  5. #define se second
  6. #define MOD 1000000007
  7. #define FOR(i,a,b) for (int i = (a);i <= (b);i++)
  8. #define FOD(i,a,b) for (int i = (b);i >= (a);i--)
  9. #define ALL(x) (x).begin(),(x).end()
  10. #define ii pair<ll,ll>
  11. #define iii pair<int,pair<int,int>>
  12. //const int MOD = 998244353;
  13. const int MAXN = 1e5 + 7;
  14. const int maxn = 1687;
  15. const ll oo = 9e18;
  16. int a[MAXN],n,m = 1;
  17. vector<ll> v,premu[maxn],tmp;
  18. bool f[19];
  19. ll ans = -oo;
  20. void cre(int id){
  21.     if (!id){
  22.         for (auto x : tmp)premu[m].push_back(x);
  23.         m++;
  24.         return ;
  25.     }
  26.     FOR(i,1,9)if (!f[i]){
  27.         f[i] = true;tmp.push_back(i);
  28.         FOR(j,i + 1,9)if (!f[j]){
  29.             f[j] = true;tmp.push_back(j);
  30.             FOR(k,j + 1,9)if (!f[k]){
  31.                 f[k] = true;tmp.push_back(k);
  32.                 cre(id - 1);f[k] = false;tmp.pop_back();
  33.             }
  34.             f[j] = false;tmp.pop_back();
  35.         }
  36.         f[i] = false;tmp.pop_back();
  37.     }
  38. }
  39. ll check(){
  40.     ll ans = -oo;
  41.     FOR(i,1,m - 1){
  42.         ll res = 0;
  43.         for (int j = 0;j < 9;j += 3)
  44.         res = res + v[premu[i][j]] * v[premu[i][j + 1]] * v[premu[i][j + 2]];
  45.         ans = max(ans,res);
  46.     }
  47.     return ans;
  48. }
  49. void sub1(int mask = n){
  50.     cre(3);
  51.     FOR(i,1,(1<<mask) - 1)
  52.     if (__builtin_popcount(i) == 9){
  53.         v.clear();v.push_back(0);
  54.         FOR(j,0,mask - 1)if (i >> j & 1)
  55.         v.push_back(a[j + 1]);
  56.         ans = max(ans,check());
  57.     }
  58.     cout << ans;
  59. }
  60. void sub2(){
  61.     sort(a+1,a+1+n);
  62.     FOR(i,10,18)a[i] = a[n - i + 10];
  63.     n = 18;sub1();
  64. }
  65. int main(){
  66.     ios_base::sync_with_stdio(false);
  67.     cin.tie(0); cout.tie(0);
  68.     cin >> n;
  69.     FOR(i,1,n)cin >> a[i];
  70.     if (n <= 18)sub1();
  71.     else sub2();
  72.     return 0^0;
  73. }
  74.  
Success #stdin #stdout 0.68s 5264KB
comments (?)
stdin
copy 
19
-1 -1 -1 -1 -1 -1 -1 -1 -1 1 2 3 4 5 6 7 8 9 -100
stdout
copy 
1600
https://ideone.com/wRYhMu
language:
C++ (gcc 8.3)
created:
3 days 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!