fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const int N = 105;
  7.  
  8. int n, k[N], f[N][16][16];
  9. ll ans[N][16][16];
  10.  
  11. void solve() {
  12.     cin >> n;
  13.     for (int i = 1; i <= n; i++) cin >> k[i];
  14.  
  15.     memset(f, -1, sizeof f);
  16.     for (int c = 0; c < 16; c++) {
  17.         if (k[1] > 0 && ((c >> (k[1] - 1)) & 1)) continue;
  18.         f[1][c][0] = __builtin_popcount(c);
  19.         ans[1][c][0] = 1;
  20.     }
  21.  
  22.     for (int i = 2; i <= n; i++)
  23.         for (int c = 0; c < 16; c++) {
  24.             if (k[i] > 0 && ((c >> (k[i] - 1)) & 1)) continue;
  25.             int cnt = __builtin_popcount(c);
  26.             for (int p = 0; p < 16; p++) {
  27.                 if (((p << 2) & c) || ((p >> 2) & c)) continue;
  28.  
  29.                 for (int pp = 0; pp < 16; pp++) {
  30.                     if (f[i - 1][p][pp] == -1) continue;
  31.  
  32.                     if (((pp << 1) & c) || ((pp >> 1) & c)) continue;
  33.  
  34.                     int val = f[i - 1][p][pp] + cnt;
  35.                     if (f[i][c][p] < val) {
  36.                         f[i][c][p] = val;
  37.                         ans[i][c][p] = ans[i - 1][p][pp];
  38.                     } else if (f[i][c][p] == val) ans[i][c][p] += ans[i - 1][p][pp];
  39.                 }
  40.             }
  41.         }
  42.     int M = -1; ll L = 0;
  43.     for (int c = 0; c < 16; c++)
  44.         for (int p = 0; p < 16; p++)
  45.             if (M < f[n][c][p]) {
  46.                 M = f[n][c][p];
  47.                 L = ans[n][c][p];
  48.             } else if (M == f[n][c][p]) L += ans[n][c][p];
  49.     cout << M << " " << L << "\n";
  50. }
  51.  
  52. int main() {
  53.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  54.  
  55.     #define TASK "NGHT"
  56.     if (fopen(TASK".INP", "r")) {
  57.         freopen(TASK".INP", "r", stdin);
  58.         freopen(TASK".OUT", "w", stdout);
  59.     }
  60.  
  61.     int tests = 1; // cin >> tests;
  62.     while (tests--) solve();
  63.  
  64.     #ifndef ONLINE_JUDGE
  65.     cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  66.     #endif
  67.  
  68.     return 0;
  69. }
  70.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
2
1
0
stdout
copy 
4 8
https://ideone.com/nEeJO7
language:
C++14 (gcc 8.3)
created:
1 day 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!