fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
  4. #define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
  5. #define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
  6. #define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
  7. #define ALL(v) (v).begin(),(v).end()
  8. #define pb push_back
  9. #define mp make_pair
  10. #define fi first
  11. #define se second
  12. #define SZ(x) ((int)(x).size())
  13. #define double db
  14. typedef long long ll;
  15. typedef pair<int,int> PII;
  16. const ll mod=1000000007;
  17. ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
  18. const int MAXN = 200;
  19. const int oo = (1 << 6) - 1;
  20.  
  21. int n, x, ans1, f[MAXN][oo+3], a[5][MAXN], z[MAXN];
  22. ll ans2, t[MAXN][oo+3];
  23.  
  24. bool getbit(int state, int i) {
  25.     return (state >> (6-i) ) & 1;
  26. }
  27.  
  28. int tinh(int state) {
  29.     int res = 0;
  30.     FOR(i,1,6)
  31.     if (getbit(state,i)) res++;
  32.     return res;
  33. }
  34.  
  35. int main() {
  36.     	ios_base::sync_with_stdio(0); cin.tie(0);
  37.     	#ifndef ONLINE_JUDGE
  38.     	freopen("test.inp", "r", stdin);
  39.     	freopen("test.out", "w", stdout);
  40.     	#endif
  41.     cin >> n;
  42.     FOR(i,1,n) {
  43.         cin >> x;
  44.         if (x) a[x][i] = 1;
  45.     }
  46.     FOR(i,1,3) {
  47.         z[1] = z[1] * 2 + a[i][1];
  48.     }
  49.     FOR(i,2,n) {
  50.         FOR(j,1,3) z[i] = z[i] * 2 + a[j][i-1];
  51.         FOR(j,1,3) z[i] = z[i] * 2 + a[j][i];
  52.     }
  53.     f[0][0] = 0; t[0][0] = 1;
  54.     FOR(j,0,(1<<3)-1)
  55.     if ((z[1]&j)==0) {
  56.         f[1][j] = tinh(j);
  57.         t[1][j] = 1;
  58.     }
  59.     FOR(i,2,n) {
  60.         FOR(state,0,oo)
  61.         if ((z[i]&state)==0)
  62.         FOR(j,0,oo)
  63.         if ((z[i-2]&j)==0)
  64.         if (t[i-2][j]>0)
  65.         if ((i>3||(i==2&j==0))||(i==3&j<(1<<3)))
  66.         {
  67.             // check ma
  68.             bool ok = 1;
  69.             if (getbit(state,1)) {
  70.                 if (getbit(state,6)) ok = 0;
  71.                 if (getbit(j,6)) ok = 0;
  72.                 if (getbit(j,2)) ok = 0;
  73.             }
  74.             if (getbit(state,2)) {
  75.                 if (getbit(j,1)) ok = 0;
  76.                 if (getbit(j,3)) ok = 0;
  77.             }
  78.             if (getbit(state,3)) {
  79.                 if (getbit(state,4)) ok = 0;
  80.                 if (getbit(j,2)) ok = 0;
  81.                 if (getbit(j,4)) ok = 0;
  82.             }
  83.             if (getbit(state,4)) {
  84.                 if (getbit(state,3)) ok = 0;
  85.                 if (getbit(j,5)) ok = 0;
  86.             }
  87.             if (getbit(state,5)) {
  88.                 if (getbit(j,4)) ok = 0;
  89.                 if (getbit(j,6)) ok = 0;
  90.             }
  91.             if (getbit(state,6)) {
  92.                 if (getbit(j,5)) ok = 0;
  93.                 if (getbit(state,1)) ok = 0;
  94.             }
  95.             // qhd
  96.             if (ok)
  97.             if (f[i][state]<f[i-2][j]+tinh(state)) {
  98.                 f[i][state] = f[i-2][j] + tinh(state);
  99.                 t[i][state] = t[i-2][j];
  100.             }
  101.                 else
  102.             if (f[i][state]==f[i-2][j]+tinh(state)) {
  103.                 t[i][state] += t[i-2][j];
  104.             }
  105.         }
  106.     }
  107.     FOR(state,0,oo) ans1 = max(ans1,f[n][state]);
  108.     FOR(state,0,oo)
  109.     if (f[n][state]==ans1) ans2 += t[n][state];
  110.     cout << ans1 << " " << ans2;
  111. 	return 0;
  112. }
  113.  
Success #stdin #stdout 0s 15400KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 1
https://ideone.com/SBrfu8
language:
C++14 (clang 8.0)
created:
6 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!