fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct hired_t
  6. {
  7.     int battles, size;
  8.  
  9.     hired_t( int s ) : battles( 0 ), size( s ) {}
  10. };
  11.  
  12. struct state_t: vector< hired_t >
  13. {
  14.     int cost, encountered, hired;
  15.  
  16.     state_t() : cost( 0 ), encountered( 0 ), hired( 0 ) {}
  17.  
  18.     bool operator < ( const state_t &s ) const
  19.     {
  20.         if ( cost != s.cost )
  21.             return ( cost < s.cost );
  22.  
  23.         if ( encountered != s.encountered )
  24.             return ( encountered < s.encountered );
  25.  
  26.         return hired > s.hired;
  27.     }
  28.  
  29.     void battle( int t )
  30.     {
  31.         int u; stack< vector::iterator > erased;
  32.  
  33.         for( auto it = begin(), iu = end(); it != iu; it++, t -= u, hired -= u )
  34.             if ( ( it->size -= ( u = min( t, it->size ) ) ) == 0 || ++(it->battles) == 3 )
  35.                 hired -= it->size, erased.push( it );
  36.  
  37.         while( !erased.empty() )
  38.             erase( erased.top() ), erased.pop();
  39.     }
  40.  
  41.     void hire( int t )
  42.     {
  43.         emplace_back( t ), hired += t;
  44.     }
  45.  
  46. } initial_state;
  47.  
  48. struct states_t: set< state_t >
  49. {
  50.     int min_cost, N, next; struct group_t { int size, cost; } g, group[ 20 ];
  51.  
  52.     states_t(): min_cost( INT_MAX )
  53.     {
  54.         cin >> N, insert( initial_state );
  55.  
  56.         for( int i = 0; i < N; i++ )
  57.             cin >> group[ i ].size >> group[ i ].cost;
  58.     }
  59.  
  60.     void goal_state( const state_t &present )
  61.     {
  62.         if ( present.cost >= min_cost )
  63.             return;
  64.  
  65.         min_cost = present.cost;
  66.     }
  67.  
  68.     void candidate_state( const state_t &present )
  69.     {
  70.         if ( present.cost < min_cost )
  71.             insert( present );
  72.     }
  73.  
  74.     void battle( state_t present )
  75.     {
  76.         if ( present.encountered < N )
  77.             present.battle( g.size ), candidate_state( present );
  78.         else
  79.             goal_state( present );
  80.     }
  81.  
  82.     void pass( state_t present )
  83.     {
  84.         present.cost += g.cost;
  85.  
  86.         if ( present.encountered < N )
  87.             candidate_state( present );
  88.         else
  89.             goal_state( present );
  90.     }
  91.  
  92.     void hire( state_t present )
  93.     {
  94.         present.cost += 2 * g.cost, present.hire( g.size ), candidate_state( present );
  95.     }
  96.  
  97.     void iterate()
  98.     {
  99.         auto it = begin();
  100.  
  101.         if ( it->cost >= min_cost )
  102.         {
  103.             erase( it ); return;
  104.         }
  105.  
  106.         state_t present( *it ); erase( it ), g = group[ present.encountered++ ];
  107.  
  108.         if ( present.hired >= g.size )
  109.             battle( present );
  110.  
  111.         pass( present );
  112.  
  113.         if ( present.encountered < N )
  114.             hire( present );
  115.     }
  116. };
  117.  
  118. int main()
  119. {
  120.     ios_base::sync_with_stdio( false ), cin.tie( nullptr ), cout.tie( nullptr );
  121.  
  122.     int T; cin >> T;
  123.  
  124.     while( T-- )
  125.     {
  126.         states_t states;
  127.  
  128.         while( !states.empty() )
  129.             states.iterate();
  130.  
  131.         cout << states.min_cost << '\n';
  132.     }
  133. }
Success #stdin #stdout 0s 4516KB
comments (?)
stdin 
1
7
2 1
2 1
1 1
1 1
1 1
1 2
2 2
stdout 
7
https://ideone.com/oRsP2k
language:
C++14 (gcc 8.3)
created:
6 years 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!