fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp> // Common file
  3. #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6. #define line '\n'
  7. #define khaled ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  8. long long derangement(int n){if(n == 0)return 1;if(n == 1)return 0;if(n == 2)return 1;return (n - 1)*(derangement(n - 1) + derangement(n - 2));}
  9. bool line_checking(long long a1,long long b1,long long a2,long long b2,long long a3,long long b3){return (a3-a1)*(b2-b1)==(a2-a1)*(b3-b1);}
  10. bool valid(long long i,long long j,long long n,long long m){return i>=0&&i<n&&j>=0&&j<m;}
  11. long long safe_mul_mod(long long a,long long b,const long long &mod){long long res=0,y=a%mod;while(b>0){if(b&1){res=((res%mod)+(y%mod))%mod;}y=((y%mod)*(2ll%mod))%mod;b>>=1;}return (res%mod);}
  12. long long mul(long long x,long long y,const long long&mod){return ((x%mod)*(y%mod))%mod;}
  13. long long add(long long x,long long y,const long long&mod){return (((x%mod)+(y%mod))%mod+mod)%mod;}
  14. long long fast_power(long long base,long long power,const long long &m=INT64_MAX){if (power == 1 || power == 0)return base * power + (!power);long long res = (fast_power(base, power / 2, m) % m) % m;if (power & 1)return mul(base,mul(res,res,m),m);else return mul(res,res,m);}
  15. long long mod_inverse_fermat(long long B,const long long&mod=1e9+7){ return fast_power(B,mod-2,mod);}//mod is prime
  16. vector<int>mod_inverse_for_range(int n,int p){vector<int>inv(n+1,1);for(int i=2;i<n+1;i++) {inv[i] = ( p - (p / i) * inv[p % i] % p ) % p;}return inv;}//mod is prime
  17. vector<long long>factorial(long long n,const long long& mod){vector<long long>v(n+1,1);for(int i=2;i<=n;i++)v[i]=mul(i,v[i-1],mod);return v;}
  18. long long NCR_MOD(long long n, long long r,vector<long long>&fact,const long long&mod){return mul(mul(fact[n], mod_inverse_fermat(fact[n - r], mod), mod), mod_inverse_fermat(fact[r], mod), mod);}
  19. long long phi(long long n) {long long result = n;for (int i = 2; i * i <= n; i++) {if (n % i == 0) {while (n % i == 0)n /= i;result -= result / i;}}if (n > 1)result -= result / n;return result;}
  20. long double NCR_LINEAR_TIME(long long n,long long r){if(r>n)return 0;if(r==0||r==n){return 1;}if(r==1||r==n-1)return n;return NCR_LINEAR_TIME(n-1,r-1)*(long double)n/r;}
  21. bool power_of_two(int n) { n=abs(n);  return n && !(n & (n - 1));}
  22. int dx[]{1,-1,0,0,1,1,-1,-1};//0->4 normal,4->8 diagonal
  23. int dy[]{0,0,1,-1,1,-1,1,-1};
  24. const long double pi=3.14159265350979323846;
  25. const long double Eps=1e-10;
  26. #define int __int128
  27. template<class integer>
  28. inline integer to_int(const string& s, size_t* idx = 0, int base = 10) {
  29.     size_t n = s.size(), i = idx ? *idx : 0; bool sign = false; integer x = 0;
  30.     if (s[i] == '-')
  31.         ++i, sign = true;
  32.     function<int(char)> char_to_digit = [&](char c) {
  33.         static const int d[] = {'a'-10,'0'};
  34.         return tolower(c)-d[isdigit(c)]; };
  35.     while (i < n)
  36.         x *= base, x += char_to_digit(s[i++]);
  37.     if (idx)
  38.         *idx = i;
  39.     return sign ? -x : x; }
  40.  
  41. template<class integer>
  42. inline string to_string(integer x, int base = 10) {
  43.     bool sign = false; string s;
  44.     if (x < 0)
  45.         x = -x, sign = true;
  46.     function<char(int)> digit_to_char = [](int d) {
  47.         static const char c[] = {'a'-10,'0'};
  48.         return c[d < 10]+d; };
  49.     do
  50.         s += digit_to_char(x%base), x /= base;
  51.     while (x > 0);
  52.     if (sign)
  53.         s += '-';
  54.     reverse(s.begin(),s.end());
  55.     return s; }
  56.  
  57. template<class integer>
  58. inline istream& read(istream& is, integer& x) {
  59.     string s; is >> s, x = to_int<integer>(s); return is; }
  60.  
  61. template<class integer>
  62. inline ostream& write(ostream& os, integer x) { return os << to_string(x); }
  63.  
  64. using  lll =   signed __int128;
  65. using ulll = unsigned __int128;
  66.  
  67. inline istream& operator>>(istream& is,  lll &x) { return  read(is,x); }
  68. inline istream& operator>>(istream& is, ulll &x) { return  read(is,x); }
  69. inline ostream& operator<<(ostream& os,  lll  x) { return write(os,x); }
  70. inline ostream& operator<<(ostream& os, ulll  x) { return write(os,x); }
  71. template<typename T>
  72. using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
  73. const int N=1e5+1;
  74. const int mod=1e9+7;
  75. int inf=1;
  76. /*--------------------------------------------------------------------------------------------------------------------*/
  77. /*--------------------------------------------------------------------------------------------------------------------*/
  78. int c(int n,int k){
  79.     int res=0;
  80.     while(n){
  81.         if(n%10==k)res++;
  82.         n/=10;
  83.     }
  84.     return res;
  85. }
  86. int dp[101][3][3][3][3][3][3][3][3][3][3];
  87. vector<vector<int>>dlog;
  88. int solve(int index,vector<int>&v,int zero,int one,int two,int three,int four,int five,int six,int seven,int eight,int nine){
  89.     if(zero>2||one>2||two>2||three>2||four>2||five>2||six>2||seven>2||eight>2||nine>2)return -inf;
  90.     if(index==v.size()){
  91.        return 0;
  92.     }
  93.     int &ret=dp[index][zero][one][two][three][four][five][six][seven][eight][nine];
  94.     if(~ret)return ret;
  95.     int res1=solve(index+1,v,zero+dlog[index][0],one+dlog[index][1],two+dlog[index][2],three+dlog[index][3],four+dlog[index][4],five+dlog[index][5],six+dlog[index][6],
  96.                    seven+dlog[index][7],eight+dlog[index][8],nine+dlog[index][9])+v[index];
  97.     int res2=solve(index+1,v,zero,one,two,three,four,five,six,seven,eight,nine);
  98.     return ret =  max(res1,res2);
  99. }
  100. signed main() {
  101.     khaled
  102.     int t;
  103.     cin>>t;
  104.     int l=30;
  105.     while(l--)
  106.         inf=inf*10;
  107.     while(t--){
  108.         int n;
  109.         cin>>n;
  110.         for(int i=0;i<n;i++)memset(dp[i],-1,sizeof(dp[i]));
  111.         dlog.clear();
  112.         vector<int>v(n);
  113.         dlog.resize(n,vector<int>(10));
  114.         for(auto &val:v)cin>>val;
  115.         for(int j=0;j<n;j++){
  116.             for(auto &i:{0,1,2,3,4,5,6,7,8,9})
  117.                 dlog[j][i]=c(v[j],i);
  118.         }
  119.         cout<<solve(0,v,0,0,0,0,0,0,0,0,0,0)<<line;
  120.     }
  121. }
Success #stdin #stdout 0.01s 5408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/VHzyiw
language:
C++ (gcc 8.3)
created:
2 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!