fork(1) download 
  1. #include<bits/stdc++.h>
  2.  
  3. #define llu unsigned long long
  4. #define ll long long
  5. #define pi 3.141592
  6. #define nl printf("\n")
  7. #define f(i,l1,l2) for(i=l1;i<l2;i++)
  8. #define gc getchar_unlocked
  9. #define vi vector<int>
  10. #define vit vi::iterator
  11. #define all(c) c.begin(), c.end()
  12. #define pb push_back
  13. #define endl "\n"
  14. using namespace std;
  15.  
  16. /*void fin(int &x)       //does not compile in codeblocks but does in online judges
  17. {                        //use if input too large ( only for integers )
  18. int i=0;x=0;
  19. register int c=gc();
  20. while(c<48||c>57)
  21. c=gc();
  22. while(c>47&&c<58)
  23. {
  24. x=(x<<1)+(x<<3) + c-48;
  25. i++;
  26. c=gc();
  27. }
  28. }*/
  29. int n,m;
  30. int a[19];
  31. int ab[19][19];
  32. int dp[1<<18][18][19];
  33. map<string,int> h;
  34.  
  35. int func(int mask, int i, int k)
  36. {
  37.     //cout<<i<<" "<<k<<endl;
  38.     if(!mask)
  39.         return 0;
  40.     int ans = dp[mask][i][k];
  41.  
  42.     if(ans!=-1)
  43.       return ans;
  44.  
  45.     int j;
  46.     f(j,0,n)
  47.     {
  48.         if(mask&(1<<j))
  49.         {
  50.             if(ab[i][j]!=INT_MIN)
  51.                 {ans = max(ans, func(mask&(~(1<<j)),j,k+1) + (k)*a[j]);
  52.                 //cout<<ans<<" "<<k<<" "<<i<<" "<<endl;
  53.                 }
  54.         }
  55.     }
  56.     return (dp[mask][i][k] = ans);
  57. }
  58.  
  59. int main()
  60. {
  61.     //std::ios::sync_with_stdio(false);
  62.     //cin.tie(0);
  63.     int t,i,j,e;
  64.     cin>>t;
  65.     while(t--)
  66.     {
  67.         cin>>n>>m;
  68.         cin.ignore();
  69.         f(i,0,n)
  70.         {
  71.  
  72.             char rr[50];
  73.             gets(rr);
  74.             int len = strlen(rr);
  75.             //cout<<a;
  76.             int pos;
  77.             for(int g=len-1; g>=0; g--)
  78.             {
  79.                 if(rr[g]==' ')
  80.                 {
  81.                     pos = g;
  82.                     break;
  83.                 }
  84.             }
  85.             string s;
  86.             for(int g=0; g<=pos-1; g++)
  87.                 s.pb(rr[g]);
  88.             int y=0;
  89.             for(int g=pos+1; g<len; g++)
  90.             {
  91.                 y = y*10 + (rr[g]-'0');
  92.             }
  93.             h[s] = i;
  94.             a[i] = y;
  95.             //cout<<s<<":";
  96.             //cout<<y<<endl;
  97.  
  98.  
  99.         }
  100.         map<string,int> :: iterator it;
  101.         /*for(it= h.begin();it!=h.end();it++)
  102.         {
  103.             cout<<it->first<<" "<<it->second<<endl;
  104.         }*/
  105.         /*f(i,0,n)
  106.             cout<<a[i]<<" ";
  107.             cout<<endl;*/
  108.         f(i,0,19)
  109.             f(j,0,19)
  110.                 ab[i][j] = 0;
  111.  
  112.         f(i,0,m)
  113.         {
  114.             string s1,s2;
  115.             // string x;
  116.             // cin>>s1>>x>>s2;
  117.             char rr[100];
  118.             gets(rr);
  119.             int len = strlen(rr);
  120.             int hpos, apos;
  121.  
  122.             for(int g=0; g<len; g++)
  123.             {
  124.                 if(rr[g]=='-')
  125.                 {
  126.                     hpos = g;
  127.                     break;
  128.                 }
  129.             }
  130.             for(int g=0; g<len; g++)
  131.             {
  132.                 if(rr[g]=='>')
  133.                 {
  134.                     apos = g;
  135.                     break;
  136.                 }
  137.             }
  138.  
  139.             for(int g=0; g<=hpos-2; g++)
  140.             {
  141.                 s1.pb(rr[g]);
  142.  
  143.             }
  144.  
  145.             for(int g=apos+2; g<len; g++)
  146.             {
  147.                 s2.pb(rr[g]);
  148.  
  149.             }
  150.  
  151.  
  152.             // cout<<s1<<" "<<s2<<endl;
  153.             ab[h[s1]][h[s2]] = 0;
  154.             ab[h[s2]][h[s1]] = INT_MIN;
  155.         }
  156.  
  157.  
  158.  
  159.         /*f(i,0,19)
  160.             f(j,0,19)
  161.                 if(ab[i][j] != 0)
  162.                     ab[i][j] = INT_MIN;
  163.         */
  164.         f(i,0,1<<n)
  165.             f(j,0,n)
  166.                 for(int k=0;k<=n;k++)
  167.                     dp[i][j][k] = -1;
  168.  
  169.         int mask;
  170.  
  171.         int ans = 0;
  172.         f(mask,1,1<<n)
  173.         {
  174.  
  175.             f(j,0,n)
  176.             {
  177.                 //int k = 1;
  178.                 if(mask&(1<<j))
  179.                 {
  180.  
  181.                     //if(mask==7)
  182.                     //  cout<<a[j]<<" "<<k<<(mask&(~(1<<j)))<<endl;
  183.                     ans = max(ans, a[j] + func(mask&(~(1<<j)), j, 2));
  184.                 }
  185.             }
  186.         }
  187.  
  188.         /*f(i,0,1<<n)
  189.         {
  190.             f(j,0,n)
  191.             cout<<dp[i][j]<<" ";
  192.             cout<<endl;
  193.         }*/
  194.  
  195.  
  196.         cout<<ans<<endl;
  197.  
  198.     }
  199.  
  200.     return 0;
  201. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
1
3 2
Implementation 3
Dynamic Programming 10
Greedy 7
Greedy --> Dynamic Programming
Implementation --> Dynamic Programming
compilation info 
prog.c:1:24: fatal error: bits/stdc++.h: No such file or directory
compilation terminated.
stdout 
Standard output is empty
https://ideone.com/WMuhiH
language:
C (gcc 8.3)
created:
9 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!