fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. string dp[(1024*1024)+5];
  5. int kolejna[(1024*1024)+5][10];
  6. int ile[10];
  7.  
  8. int main()
  9. {
  10.     int n,x;
  11.     string slo,slo1;
  12.     cin >> n >> slo;
  13.     for(int i = 0;i < 1024*1024;++i)
  14.     {
  15.         bitset<20> maska(i);
  16.         bitset<20> maska1(i);
  17.         for(int j = 0;j <= 9;++j)
  18.         {
  19.             kolejna[(int)maska.to_ullong()][j] = (int)maska.to_ullong() | maska1.to_ullong();
  20.             if(maska1[n-1])
  21.             {
  22.                 maska1[n-1] = 0;
  23.                 maska1 <<= 1;
  24.                 maska1[0] = 1;
  25.             }
  26.             else
  27.             {
  28.                 maska1 <<= 1;
  29.             }
  30.         }
  31.     }
  32.     for(int i = 1;i < 10;++i)
  33.     {
  34.         kolejna[0][i] = (1 << i);
  35.     }
  36.     for(int i = 0;i < (int)slo.size();++i)
  37.     {
  38.         ile[slo[i]-'0']++;
  39.         if(ile[slo[i]-'0'] <= 20)
  40.         {
  41.             slo1 += slo[i];
  42.         }
  43.     }
  44.     int wyn = -1,maks = -1;
  45.     //bitset<20> tak(kolejna[94][5]);
  46.     //cout << tak;
  47.     for(int i = 0;i < (int)slo1.size();++i)
  48.     {
  49.         x = slo1[i]-'0';
  50.         //cout << x;
  51.         for(int j = (1 << n)-1;j >= 0;--j)
  52.         {
  53.             bitset<20> obc(j);
  54.             bitset<20> kolj(kolejna[j][x]);
  55.             kolj = kolj|obc;
  56.             if(kolj[0]) continue;
  57.             //cout << kolj << endl;
  58.             if(dp[j].size()+1 > dp[kolj.to_ullong()].size())
  59.             {
  60.                 dp[kolj.to_ullong()] = dp[j];
  61.                 dp[kolj.to_ullong()] += slo[i];
  62.                 if(((int)dp[kolj.to_ullong()].size() > maks) && (!kolj[0]))
  63.                 {
  64.                     wyn = kolj.to_ullong();
  65.                     maks = dp[kolj.to_ullong()].size();
  66.                 }
  67.             }
  68.         }
  69.     }
  70.     cout << maks << endl << dp[wyn];
  71. }
Success #stdin #stdout 0.03s 77408KB
comments (?)
stdin
copy 
7
123456
stdout
copy 
4
1235
https://ideone.com/Bp3qfP
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!