fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <random>
  4. using namespace std;
  5.  
  6. using ll = long long;
  7.  
  8. const ll T = 18;
  9. const ll N = 18;
  10. const ll SIZE = 20;
  11.  
  12. #define rep(i, l, r) for(ll i = l; i <= r; i++)
  13.  
  14. ll A[SIZE];
  15. ll take[SIZE];
  16. ll ans;
  17. ll ANS[SIZE];
  18.  
  19. ll dp[20][2][2] = {0};
  20.  
  21. ll DFS(ll depth){
  22.     if( depth > N ){
  23.         ll sum = 0;
  24.  
  25.         rep(i, 1, N) if( take[i] ){
  26.             if( i > 1 ) sum += ( A[i] * ( take[i-1] ? -1 : 1 ) );
  27.             if( i > 2 ) sum += ( A[i] * ( take[i-2] ? 1 : -1 ) );
  28.         }
  29.  
  30.         return ans = max(ans, sum);
  31.     }
  32.  
  33.     take[depth] = 0; DFS(depth+1);
  34.     take[depth] = 1; DFS(depth+1);
  35.  
  36.     return 1;
  37. }
  38.  
  39. ll DP(){
  40.     rep(i, 1, N){
  41.         if( i == 1 ) continue;
  42.  
  43.         if( i == 2 ){
  44.             dp[i][0][0] = dp[i-1][0][0];
  45.             dp[i][0][1] = dp[i-1][1][0];
  46.             dp[i][1][0] = dp[i-1][0][0] + A[i];
  47.             dp[i][1][1] = dp[i-1][1][0] - A[i];
  48.             continue;
  49.         }
  50.  
  51.         dp[i][0][0] = max( dp[i-1][0][0], dp[i-1][0][1] );
  52.         dp[i][0][1] = max( dp[i-1][1][1], dp[i-1][1][0] );
  53.         dp[i][1][0] = max( dp[i-1][0][0], dp[i-1][0][1] + 2 * A[i] );
  54.         dp[i][1][1] = max( dp[i-1][1][0] - 2 * A[i], dp[i-1][1][1] );
  55.     }
  56.  
  57.     return ans = max(0LL, max( max( dp[N][0][0], dp[N][0][1] ), max( dp[N][1][0], dp[N][1][1] ) ) );
  58. }
  59.  
  60. int main() {
  61.  
  62.     rep(t, 1, T){
  63.         rep(i, 1, N) cin >> A[i];
  64.  
  65.         // 全不選 = 0
  66.         ans = 0;
  67.  
  68.         // DFS
  69.         fill(take, take+SIZE, 0);
  70.         DFS(1);
  71.  
  72.         // DP
  73.         // fill(&dp[0][0][0], &dp[20][2][2], 0);
  74.         // DP();
  75.  
  76.         cout << ans << '\n';
  77.     }
  78.  
  79.  
  80.  
  81.     return 0;
  82. }
  83.  
  84. /*
  85.  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
  86.  */
  87.  
Success #stdin #stdout 0.26s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
https://ideone.com/wTrEhJ
language:
C++14 (gcc 8.3)
created:
13 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!